1.Formation control

Formation control of multi-vehicle systems has been studied extensively in the literature with the hope that through efficient coordination many inexpensive, simple vehicles, can achieve better performance than a single vehicle. There are some typical approaches that have been applied in formation control.

1.1 Leader-following approach

Leader-following approach refers to the case that one of the robots is designated as the leader, with the rest being followers. The follower robots need to position themselves relative to the leader and maintain a desired relative position with respect to the leader.

In [1], the authors assigned a proper subset of the fleet as group leaders or guardians whose motions will serve as reference motion for the remaining mobile robots. Then, they studied various schemes for generating the desired formation patterns and derived explicit control laws for formation keeping and relative attitude alignment based on nearest neighbor-tracking. [2], [3] considered formation control of multiple nonholonomic mobile robots by applying leader following approach. A controller based on input-output linearization is presented, which is locally stable.

1.2 Behavioral approach

Formation behavior in nature, like flocking and schooling, benefit the animals that use them in various ways. For instance, by grouping, animals combine their sensors to maximize the chance of detecting predator or to more efficiently forage for food. Studies of flocking and schooling show that these behaviors emerge as a combination of a desire to stay in the group and yet simultaneously keep a separation distance from other members of the group. Robotics researchers have drawn from these biological studies to develop formation behaviors for both simulated agents and robots.

[4] gave a brief survey of some research on the formation behavior of robots. In the paper, the authors evaluated different formation geometries and types of formation reference. By applying motor schema approach, they enabled behaviors for moving to the destination, avoiding obstacles, and formation keeping to be simultaneously active and cooperatively combined. [5] presented a behavior-based approach to formation maneuvers which are decomposed into a sequence of maneuvers between formation patterns for groups of mobile robots. The paper presents three formation control strategies: coupled dynamics formation control, passivity-based interrobot damping and saturated control.

1.3 Virtual structure

The basic idea of virtual structure is to specify a virtual leader or a virtual coordinate frame located at the virtual center of the formation as a reference for the whole group such that each vehicle's desired states can be defined relative to the virtual leader or the virtual coordinate frame.

In [6], the authors simulated and implemented the formation control algorithm based on virtual structure. From the result, they demonstrated that this approach is capable of achieving high precision movement that is fault tolerant and exhibits graceful degradation of performance. Leader selection as in other cooperative robotic strategies is not required for the algorithm. Inherently highly flexibility in the kinds of geometric formations is presented. The virtual structure approach was applied to formations of space-craft in free space is described in [7] and [8]. [9] compares the strengths and weakness of the Leader-following, behavioral and virtual structure approaches. The authors also introduced an architecture that unifies the three approaches discussed. They demonstrated the application of this architecture to the problem of synthesizing a deep-space, free-flying, multiple spacecraft interferometer.

1.4 Graph rigidity based approach

The concept of "Rigidity" comes from mathematics, mechanical and civil engineering. It refers to the property of an object that it strongly resists changing its shape, such as "rigid framework", "structural rigidity". Researcher took into account this concept in formation control and defined the rigidity as rigid motion is the only kind of motion it can undergo along any trajectory on which the lengths of all links in the set of maintained links remain constant. The rigid motion is referred to a motion along a trajectory such that the Euclidean distance between each pair of points remains constant.

[10] introduced the concept of formation rigidity and presented a systematic way of maintaining rigidity in case of vehicle removals in formations for coordinating mobile autonomous vehicles with limited communication/sensing links. [11] presented a stable control strategy for groups of vehicles to move and reconfigure cooperatively in response to a sensed, distributed environment. Each vehicle in the group serves as a mobile sensor and the vehicle network as a mobile and reconfigurable sensor array. The underlying coordination framework uses virtual bodies and artificial potentials. [12] proposed a framework for formation stabilization of multiple autonomous vehicles in a distributed way. The formation graph of the vehicles is defined and directed information flow is assumed. Natural potential functions obtained from structural constraints of a desired formation are used in formation stabilization.

1.5 Consensus-based approach

Consensus refers to the case that a group of agents, each of which has an estimate or opinion of the parameter of interest, through communication reach an agreement over the value of the parameter.

The introduction of consensus in to control area came from [13]. In this paper, the authors proposed a simple but compelling discrete-time model of autonomous agents all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its "neighbors". [14] provided a theoretical explanation for this observed behavior. In addition, the authors derived convergence results for several other similarly inspired models, such as leader-follower case, no leader case. Another of key contribution came from [15]. In that paper, the authors discussed consensus problems for networks of dynamic agents with fixed and switching topologies. Three different cases are analyzed and consensus protocols are proposed with detailed derivation.

In formation control, [16] introduced the consensus algorithm to tackle formation control problems by appropriately choosing information states on which consensus is reached. the authors shows that even in the absence of centralized leadership, the consensus based formation control strategies can guarantee accurate formation maintenance in the general case that information flow is unidirectional. Later, in [17], consensus algorithm is unified with virtual structure approach in large scale formation control applications. This unified formation control scheme accommodates an arbitrary number of group leaders and arbitrary information flow between vehicles. It only requires local neighbor-to-neighbor information exchange.

2.Project description

The project is based on [16] and [17]. Here we consider a 2D formation control problem. Every agent can exchange information with every other one. However, the received information will be corrupted by communication noise, which is modeled by Additive white Gaussian noise (AWGN channel). Communication between robots will be taken into account, because of the limit of bandwidth or distance separation. In the formation control scheme, we will consider vehicles with single-integrator dynamics. The unified formation control scheme of consensus-based approach and virtual structure proposed in [17] will be applied. The group of robots will reach consensus over the position of virtual structure through noisy communication channel and will calculate its desired position relative to the virtual leader. With the desired position, feedback control law will be applied to drive each robot to its corresponding position.

3.Reference

[1] P. K. C. Wang and F. Y. Hadaegh, "Coordination and control of multiple microspacecraft moving in formation," The Journal of the Astronautical Sciences, vol. 44, no. 3, pp. 315-355, 1996.

[2] J. P. Desai, J. Ostrowski and V.J. Kumar, "Controlling Formations of Multiple Mobile Robots," Proc. IEEE Int. Robotics & Automation, May, 1998, pp.2864-2869.

[3] Aveek K. Das, et al, "A Vision-Based Formation Control Framework", IEEE Trans. On Robotics and Automation, Vol. 18, NO. 5, Oct. 2002, pp.813-825.

[4] T. Balch and R. C. Arkin, "Behavior-based formation control for multirobot teams," IEEE J. Robot. Automat., vol. 14, no. 6, pp. 926-939, December 1998.

[5] J. R. Lawton, R. W. Beard, and B. Young, "A decentralized approach to formation maneuvers," IEEE J. Robot. Automat., vol. 19, no. 6, pp. 933-941, December 2003.

[6] M. A. Lewis and K.-H. Tan, "High precision formation control of mobile robots using virtual structures," Autonomous Robots, vol. 4, pp. 387-403, 1997.

[7] R. W. Beard and F. Y. Hadaegh, "Constellation templates: An approach to autonomous formation flying," in Proc. World Automat. Congress. Anchorage, AK: ISIAC, May 1998, pp. 177.1-177.6.

[8] R.W. Beard, "Architecture and algorithms for constellation control," Jet Propulsion Lab., California Inst. Technol., Pasadena, CA, Tech. Rep., Mar. 1998.

[9] R. W. Beard, J. R. Lawton, and F. Y. Hadaegh, "A coordination architecture for spacecraft formation control," IEEE Trans. Contr. Syst. Technol., vol. 9, no. 6, pp. 777-790, November 2001.

[10] T. Eren, P. N. Belhumeur, and A. S. Morse, "Closing ranks in vehicle formations based on rigidity," in Proc. of Conf. on Decision Contr., Las Vegas, NV, December 2002, pp. 2959-2964.

[11] P. Ogren, E. Fiorelli, and N. E. Leonard, "Cooperative control of mobile sensor networks: Adaptive gradient climbing in a distributed environment," IEEE Trans. Automat. Contr., vol. 49, no. 8, pp. 1292-1302, August 2004.

[12] R. Olfati-Saber and R. M. Murray, "Distributed cooperative control of multiple vehicle formations using structural potential functions," in IFAC World Congress, Barcelona, Spain, July 2002.

[13] T. Vicsek, A. Czirok, E. Ben Jacob, I. Cohen, and O. Schochet, "Novel type of phase transitions in a system of self-driven particles," Phys. Rev. Lett., vol. 75, pp. 1226-1229, 1995.

[14] A. Jadbabaie, J. Lin, and A. S. Morse, "Coordination of groups of mobile autonomous agents using nearest neighbor rules," IEEE Trans. Automat. Contr., vol. 48, no. 6, pp. 988-1001, June 2003.

[15] R. Olfati-Saber and R. M. Murray, "Consensus problems in networks of agents with switching topology and time-delays,"IEEE Trans. Automat. Contr., vol. 49, no. 9, pp. 1520-1533, September 2004.

[16] W. Ren, "Consensus based formation control strategies for multivehicle systems,"in Proc. of American Contr. Conf., Minneapolis, MN, June 2006, pp. 4237-4242.

[17] N. Sorensen, and W. Ren, "A Unified Formation Control Scheme with a Single or Multiple Leaders," American Control Conference, 2007. ACC '07 , vol., no., pp.5412-5418, 9-13 July 2007