Path Planning based on Genetic Algorithms and the Monte-Carlo method to Avoid Aerial Vehicle Collisions under uncertainties. Cobano, Conde, Alejo, Ollero. ICRA 2011

Reading this primarily to see what ICRA papers are like

1. The basic problem they work on is NP-Hard, so they are excused in using whatever method they like
2. Assumption is each vehicle knows initial trajectories of other vehicles in terms of waypoints
3. MC method (not sure which) is then used to estimate uncertainty of actual trajectories, due to atmospheric conditions, model of each UAV, and sensors
4. A collision-free path planning algorithm based on GAs is proposed, which plans in terms of waypoints
   1. The planning alg takes into account the uncertainty estimates which resulted from variance from MC
5. The approach is non-cooperative, which means when a future collision is predicted, a vehicle changes direction independently without consulting other vehicles
6. Considered scenario is navigation in the 2D plane, velocity is not permitted to change
7. Collisions are estimated by gridding the space and checking closeness in terms of number of grid cells separating the two
8. Fitness function of GA factors in: length of traj, deviation of traj from initial plan, distance of trajectory from static obstacles, turning angle between consecutive segments, and whether a collision occurs
   1. It is extremely strange that they say the weight for deviation is the by far the larges.  I would assume the weight related to collision is the most important
   2. There are some additional constraints: the trajectory is constrained to a maximum lengh, maximum amount of turns in path, and that collision is not allowed (I don’t understand why there is a related weight in the fitness function then)
9. They say they get near optimal results from this – which seems possible, I don’t think its so difficult
10. There is another set of criteria that is evaluated when trying to fly waypoints with MC; want low (statistical) deviation of path from original, distance from obstacles, and final location must be close to goal
11. Empirical execution time is linear in number of vehicles, but constant in number of static obstacles
12. I see why the paper got in now – they did it on a real UAV doing collision avoidance with simulated other UAVs.  I think computation is offboard

Advertisements