MAIN MENUPREVIOUS MENU---------------------------------Search CD-ROMSearch ResultsPrintCollision Avoidance for Multiple Agent SystemsDong Eui ChangDepartment of Mechanical EngineeringUniversity of CaliforniaSanta Barbara, CA, [email protected] C. Shadden, Jerrold E. Marsden, andReza Olfati-SaberDepartment of Control and Dynamical SystemsCalifornia Institute of Technology 107-81Pasadena, CA, 91125{shawn,marsden,olfati}@cds.caltech.eduAbstract—Techniques using gyroscopic forces and scalarpotentials are used to create swarming behaviors for multi-ple agent systems. The methods result in collision avoidancebetween the agents as well as with obstacles.I. INTRODUCTIONIt is intriguing how swarms of insects or flocks of birdscan travel in large, dense groups without colliding. Even inthe presence of external obstacles these agents are capableof smoothly avoiding collisions. There is strong reason tobelieve that the rules, or protocols, each constituent of thegroup follows are quite basic, and yet the collective orglobal motion is quite remarkable. It comes as no surprisethat understanding these protocols would be invaluable forengineering systems of autonomous agents, such as fleets ofunmanned air or underwater vehicles or groups of exploratoryrobots.The goal of this paper is to introduce a simple, decentral-ized control law that constituents of a group of vehicles canfollow to accomplish some specified control objective whileavoiding collision with one another and with unforeseenobstacles. In particular, we rely on the use of gyroscopicforces for collision avoidance, as described in Chang andMarsden [1]. Another paper that exploits gyroscopic forcesJusth and Krishnaprasad [4], where the authors use gy-roscopic forces to produce flocking behavior of multiplevehicles travelling at constant speed. Although we are notparticularly impelled to reproduce flocking behavior, as inthe famous work of Reynolds [8], the localized protocolsthat we developed largely to avoid collisions, do seem tocreate emergent, structured behavior when applied to largegroups of vehicles.Collision avoidance plays an important role in the contextof managing multiple vehicles, especially in the context ofair-trafficcontrol (see the work of Tomlin and coworkers, [2],[3]). Many traditional control methods for collision avoidancerely on a potential-based approach, such as in the NavigationFunction Method (NFM) of Rimon and Koditschek [9] orharmonic potential fields as in Masoud and Masoud [5].The ideas presented in the paper are inspired by the NFM.The general idea of the NFM is to create a global potentialfield to accomplish some control objective, such as gettingavehicle to travel from its initial location to some targetpoint while not colliding with any obstacles. To create thisglobal potential field, an attracting potential might be placedat the target point while repelling potentials are placed atthe locations of obstacles to push an approaching vehicleaway from the obstacle. Then the vehicle navigates usingthe gradient of the potential field as a force field.The breakthrough of the NFM was that it could be usedto show the existence of trajectories that avoid collision withany obstacles. However, this method has a few drawbacks:i) global information is needed regarding the location andshape of all the existing obstacles, ii) corresponding to anyobstacle, there exists a neighborhood that can trap the vehiclefor relatively long (or infinite) time, iii) the NFM is oftencomputationally impractical, and iv) the original NFM onlyconsiders the case of a single vehicle.Instead of relying on repelling potentials for obstacleavoidance, as in the NFM, the control law we present relieson gyroscopic forces. To motivate this, consider the situationshown in Fig. I, where three vehicles are initially equallyspaced about a circle.3 2 1 0 1 2 332 10123------Fig. 1. By using gyroscopic forces, three vehicles can move across thecircle without colliding. The vehicles are represented by the blue, black, andred dots. The disk about each dot represents the vehicle’s detection shell..As indicated in the figure, the objective of each vehicle isto simultaneously move to its antipodal point on the circle.If potential forces alone where used for collision avoidance,Proceedings of the 42nd IEEE Conference on Decision and Control Maui, Hawaii USA, December 2003TuM02-30-7803-7924-1/03/$17.00 ©2003 IEEE539the three vehicles would simply meet in the middle, pushequally on each other, and become gridlocked. However, ifgyroscopic forces are used, they can simply spin free of thissticky situation, as show in the figure.Gyroscopic forces can be thought of as steering forcessince they always act perpendicular to the direction of mo-tion. Fortunately, gyroscopic forces can be used for obstacleavoidance without affecting the global potential function thatwasconstructed to foster some control objective. Actually,gyroscopic forces do not even change the energy of thesystem, a well known and easily verified fact.It turns out that gyroscopic forces alone have somedifficulty preventing collision in large groups of vehicles.Therefore we also introduce a type of braking force thatallows the vehicles to slow down when they are getting tooclose to one another or an obstacle. Intuitively, if the vehicleis moving too fast towards an obstacle it will not have enoughtime to turn to avoid the obstacle. Therefore the braking forceis used to slow the vehicle such that it can turn in time toavoid the obstacle. As with the gyroscopic force, the brakingforce also does not change the global potential function.The control law that we present is completely decen-tralized, therefore the ability of an agent to accomplish itscontrol objective is not directly dependent on any other agent.Each vehicle has its own detection shell,within which itcan sense the relative location of neighboring vehicles orobstacles. Since the control of each vehicle is localized,the computations can as well be localized, which is veryimportant to ensure scalability of our control law to groupsthat contain a large number of agents. The methods that wepresent are equally applicable to either 2- or 3-dimensionalmotion.In this paper we only consider “swarms” of vehicles. Thatis, we do not explicitly constrain the relative location of eachvehicle. However, there are many applications where the rela-tive positioning between vehicles becomes important, such