8
$\begingroup$

I am working on a 2D space where my robot needs to follow a trajectory while avoiding some obstacles.

I've read recently about methods for path planning as "Vector Field Histogram" and the "Dynamic window approach".

Is it worth to use these kind of algorithms for a 2D space or should I go with something as Potential Fields or Rapidly-Exploring Random Trees?

Improve this question
$\endgroup$
3
  • $\begingroup$ Does this imply that you have some sort of map that's known in advance that you must combine with obstacles that you encounter in real time (in which case you must re-plan your trajectory)? $\endgroup$
    – Ian
    Oct 17, 2013 at 5:06
  • $\begingroup$ For the moment I have a map where I will put an obstacle in a known position. After thet I would like to make the obstacle dynamic. But first I have to begin from the non-moving known obstacle. $\endgroup$
    – Spyros
    Oct 17, 2013 at 16:38
  • $\begingroup$ Fair, but changing the problem changes the solution. Each of these algorithms exists for a specific purpose, and right now your question is too broad to say which might be appropriate. The more details you can provide on the problem (how fast the vehicle needs to react to changes in the environment, how quickly it needs to generate plans, etc), the more accurate of an answer we can give. $\endgroup$
    – Ian
    Oct 17, 2013 at 17:54

2 Answers 2

Reset to default
2
$\begingroup$

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 flying 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 obstacles.
  • 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 intensive.
  • 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.

Improve this answer
$\endgroup$
1
$\begingroup$

In a 2D space, you could probably get away with something much simpler to begin with like Breadth-first search, Dijkstra's or A-Star. Combine it with an occupancy grid as a map based on LIDAR data and you'd be good to go. RRT's work well and I've used them in the past, but for much higher dimensional search spaces. In general I would recommend starting out with the simplest solution. If it turns out it doesn't perform fast/well enough, then you upgrade to something more complicated. There's no need to build a formula-1 car to drive to the grocery store XD.

It really depends on your application, and since I know nothing about it, it's hard to give you the best answer.

Edit: RRT* (read: RRT star) is also very nice.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.