MSc Project Proposal:

Collision Avoidance for Formations using Limit Cycles

Download the project proposal


Recent years have shown an increasing interest in the use of autonomous vehicles. These vehicles can move on land (Autonomous Land Vehicles [ALV]), on water (Autonomous Surface Vessels [ASV]), under water (Autonomous Underwater Vehicles [AUV]), or in the air (Unmanned Aerial Vehicles [UAV]). Several trajectory tracking and path following algorithms have been proposed to steer the vehicles along a path in the desired formation shape, but collision avoidance between the formation members is often considered to be 'future work'.

In order to prevent collisions with obstacles, some avoidance methods must be used. One popular method is based on potential fields, and it models the obstacles as repulsive potentials and the goal as an attractive potential [1]. Since the potential field can have local minima, vehicles can get trapped at locations other than the goal location. This problem is a significant drawback of the potential field method.

Recently, another collision-avoidance method based on limit cycles has been proposed in [2], where it is applied to robot soccer. Here the other robots are seen as static obstacles, with a circular safety bound around them that the other vehicles should not enter. This limit cycle navigation method has been combined with trajectory tracking in [3].

Figure 1: Ellipsoidal limit cycle with several trajectories

Since the vehicles of the formation are moving, their velocities should be taken into account when predicting if two vehicles are on a collision course. Furthermore, it is more dangerous to pass in front or behind another (moving) vehicle than passing in parallel, which can be taken into account by using ellipsoidal safety bounds around the vehicles.

Another direction to investigate is collision avoidance in three-dimensional space. This would be necessary to guarantee collision-free movement underwater or in the air.

Research problems

The focus of this MSc project will lie on extending the limit cycle method in several directions. Some of the directions that can be considered are:
* extend the method to moving obstacles
* use ellipsoidal safety bounds around obstacles (depending on the direction)
* consider both trajectory tracking and formation control with collision avoidance
* test the controller for point masses, unicycle models, and/or (marine) vehicle models
* perform a stability analysis of the closed-loop system

Figure 2: The blue vehicle should avoid collision with the moving ones


[1] O. Khatib - Real-time obstacle avoidance for manipulators and mobile robots
The International Journal of Robotics Research 5-1 (1986), p. 90-98.

[2] D.H. Kim and J.H. Kim - A real-time limit-cycle navigation method for fast mobile robots and its application to robot soccer
Robotics and Autonomous Systems 42 (2003), p. 17-30.

[3] R. Grech and S.G. Fabri - Trajectory tracking in the presence of obstacles using the limit cycle navigation method
Proceedings of the IEEE International Symposium on Intelligent Control (2005), p. 101-106.