As you can reduce the path planning and collision avoidance of aircraft down to 2D if you do not include separation by height, I will use aerospace as the example. One school of thought is that collision avoidance is different from path planning, because in high level path planning you can assume that you have complete knowledge of the other aircraft or obstacles that
you are avoiding. In collision avoidance you
are limited by the sensors available. The levels of mission planning are shown in the Figure:- Planning Hierarchy with Spatial Decomposition, collision avoidance is most
applicable to the safety or low level trajectory planning. Also shown in this figure
are the time requirements for data from each
of the systems. Collision avoidance is the
point at which, if you do not alter course
you will crash. The two places where this
can be observed are in controlled airspace
within the terminal region (airports) and where
the airways intersect. Rules of the Air dictate a set of rules, which if followed prevent this happening. Pilots are not very
good at see-and avoid as they are required
to perform stability and control, communications and high level mission planning. This
means that collisions are not detected as early
as they should be and then become a critical last second maneuver.
In large aircraft, Traffic Collision Avoidance System (TCAS) is used to make the pilots aware of
where approaching aircraft are. TCAS is a co-operative system, which works on the assumption
that both aircraft will have TCAS. If only one aircraft has TCAS, for example a large aircraft
towards a micro-light, a collision will occur. The large aircraft may turn in one direction, and the
micro-light (who has had no communication with the aircraft) may turn in the same direction. As
mentioned above the issue is with small aircraft, which are unable to carry the large, power hungry
TCAS systems. Larger gliders carry a FLARM system (The name is inspired from Flight Alarm),
which broadcasts its own position and speed vector; but this does not communicate with TCAS, it
just senses the approaching aircraft (only it has FLARM also, leaving the same problem mentioned
with the micro-light).
These systems, which will be on most aircraft in the next ten to fifteen years, have in
influenced many experts in this field, to assume that the position of all aircraft within the operating area will be known. Though it should be noted that, whilst this would be a logical conclusion to draw in controlled airspace, in uncontrolled airspace this cannot be definitively said, because it does not account for the aforementioned small aircraft that are unable to carry such systems.
In order to deal with the situations described above in uncontrolled airspace there are three types
of collision detection sensors:
- Cooperative : That tell you where they are (e.g. ADS-B)
- Passive : Take data in (e.g. Camera's)
- Active : Send out signals to receive
information back (e.g. Radar/Sonar or Lasers)
After the sensor data is acquired, in order to work out where to go, the sensor data is analysed
using Collision Avoidance Algorithms:
- Potential Fields : Real time obstacle avoidance method. `Robot
motion can be considered as a particle that moves in a gradient
vector field generated by positive and negative electric particles'
The advantage is that it is simple. The disadvantage is the local
minima condition where the robot can get stuck between two walls or
- Vortex Potential Field : In order to reduce the problem of the local minima, a vortex can be added to the potential field, the disadvantage of this is that it forces the vehicle one way round the obstacle and this can lead to a sub-optimal path.
- Bug Algorithms : Simple to find optimal leave points, the 'simplicity of these algorithms leads to a number of shortcomings. None of these algorithms take into account robot kinematics which is a severe limitation.'
- Roadmap : Captures the connectivity of the robots free space into one
dimensional curves 'If more than one continuous paths can be found,
the shortest patch might be selected according to Dijstra's algorithm
or the A* algorithm' Drawbacks are `time and storage complexities
when the environment is complex'
- 3D Geometric : 'does not require the solution of any programming
problem, thus resulting suitable for real time applications'
- Azimuth Approach : Using passive camera video feeds and image
processing techniques to spot the aircraft and detects a collision
based on change in azimuth angle. This method can be very processor
- Collision Cone : Transforms the velocities of both aircraft into
relative velocities. A safety region is drawn around the obstacle
aircraft and a cone is used to connect the region to the avoiding
aircraft. A potential collision is detected when the relative
velocities are within the cone.
A number of path planning algorithms have been discussed in the other answers so I will not repeat them here.
In conclusion you need to fully understand the problem you are dealing with before you can design a collision avoidance algorithm or path planning algorithm to suit the purpose. Many collision avoidance algorithms and path planning algorithms are compared using a simple bicycle model which may or may not be representative of your final application. If the model is not representative then its like tuning a controller for one system then implementing it on another.