Three types of cooperative motion activities are considered:

1. Collision avoidance: Each robot in the team has an assigned goal position, and the objective is to have each robot reaching its goal from its current position without collision to each other and obstacles in the environment, and achieve the task efficiently (by certain measurement of performance such as shortest time/distance and/or minimum energy);

2.Formation control: The team of robots keeps certain form of formation (such as leader-follower, geometric patterns) during the course of motion;

3. Coverage control: The team of robots is expected to cover a space efficiently, for example, complete coverage of the area as high a frequency as possible, maximize area covered in unit time, minimize repeat coverage, etc.

A key difficulty in developing cooperative control is determining the appropriate balance between the use of global information and the local information to achieve coherent cooperation without excessive communication requirements. Global information can be categorized into two types: global goals and global knowledge. The global goals indicate the overall mission that the team is required to accomplish; global knowledge refers to the information available to the cooperative team to achieve the global goals. In contrast, local information is obtained from the agent's sensory capabilities and reflects the state of the world near the agent.

A general principle guiding the design of control laws is given as: "With a careful design, global functionality can emerge from the interaction of the local control laws of individual agents". Though some approaches were developed by researchers from computer science community, formal quantification considering kinematics/dynamics of the robot has not been extensively studied. Research is undergoing to develop fundamental mechanism of robot cooperation and inference using methodologies in dynamic systems, controls, and artificial intelligence.

Motion planning algorithms for single mobile robot systems have been intensively discussed for years. In an environment that contains a set of stationary obstacles, path planning methods such as graph searching based on geometric configuration of the environment guarantee to return optimal paths (in the sense of a performance measure such as shortest distance) in polynomial time if one exists. However, motion planning in a dynamic environment with moving obstacles is inherently harder. Even for a simple case in two dimensions, the problem is NP-hard and is not solvable in polynomial time. This fact makes multiple mobile robot motion planning a difficult problem. On the other hand, broad applications in cooperative mobile robotics call for practical and efficient motion planning strategies. Simple reactive motion planning strategies cannot guarantee deadlock-free and convergence even in simple cases. A number of algorithms have been proposed towards finding collision-free and deadlock-free paths, but most of these algorithms work in limited domains, and are difficult to evaluate quantitatively due to the great variation of the premises and conditions in each approach.

Contributions were made in proposing a practical motion planning approach with combined features of previous approaches. Contrary to our knowledge of previous results on multi-robot motion planning that either obtain optimal solutions through centralized and exhaustive computing, or achieve distributed implementations without considering any optimization issues, our approach combines these two features and explicitly optimizes performance functions through a distributed implementation. It is also capable of handling outdoor rough terrain environments and real time replanning, which have not been covered much in previous literatures, and are appealing to applications in areas such as surface mining and space exploration.

Simulations are shown on a Mars-like rough terrain using a 3D vehicle planner and control simulator. The algorithm was also implemented and successfully run on a group of Nomad 200 indoor robots.

1. Most of the work in mobile robot path planning divides path planning and path tracking into separated modules: path planning is the determination of geometric path points to track; and motion control is the determination of physical input to track a path. They are solved using methods in artificial intelligence (such as heuristic search) and control theory (such as trajectory tracking), particularly when dealing with dynamic environments. Though reducing computational expenses greatly, the drawback of this type of methods is that discrete geometric path points planned in the first step cannot be efficiently tracked in the second step due to nonholonomic motion constrains. Therefore, optimality in each step cannot be combined for overall performance analysis.

2. If robot kinematic/danamic models are considered and built within the motion planning setup, the system becomes nonlinear, high dimensional, and the computational complexity increases dramatically for the optimal planning problem. The price we have to pay for a feasible solution is the sub-optimality.

Combining heuristic search method (such as D*) in AI and control theoretic methods for nonholonomic systems, we consider the nonholonomic kinematics constrains of mobile robots and design feasible trajectories. Collision avoidance criterion are explicitly constructed. Piecewise constant parameterization is used to provide analytic solutions of feasible trajectories. Global heuristic path search and regional feasible trajectories are combined in generating path planning solutions that can be implemented real time.