# An Algorithm to Find the Shortest Path through Obstacles of Arbitrary Shapes and Positions in 2D
## 1 Introduction  
The work described was initially motivated by the need to guarantee the existence of good feasible solutions in trajectory planning for unmanned aerial vehicles (UAVs). Trajectory planning for most real vehicles requires multi-objective optimization methods in order to take into account the dynamical abilities of the vehicles and the possibly numerous constraints imposed by the mission at hand. In fact, finding the best trajectory is a non-deterministic polynomial hard (NP-hard) problem [1, 2]. Due to this complexity, the quest for good solutions is tackled with heuristic methods, such as the genetic algorithm (GA), the particle swarm optimization (PSO) algorithm, the ant colony optimization (ACO) algorithm, etc., see [3, 4]. Most of these methods are efficient, at least in some sets of problems. However, because they are based on random processes, they are not guaranteed to yield a feasible solution. Undenially, most of the time they do; however, when real-world applications are concerned, one cannot be satisfied with less than a certainty that a physically possible solution will be generated. The results of the present article can be used to generate such a solution, which furthermore will possess some strong optimality features. It will generally not be the best one with respect to all of the possible criteria, but it will definitely be a very good seed for generating near optimal solutions with the help of some heuristic methods. The trajectory solution that we propose consists of three legs. The longest one is in a flight at constant altitude that is the shortest path around the obstacles of the terrain. The two other legs are, respectively, a climb from the point of departure to the desired altitude and a descent flight from this altitude to the point of arrival, see [5, 6]. Ourproposed solution to the shortest path problem is evidently applicable in any situation in which robots move in 2D.  
We assume that the boundaries of the obstacles are simple closed curves of finite length, with a finite number of discontinuities in their tangent. They do not overlap, there is a countable number of them and they are immobile. The path generator is provided with a representation of the whole 2D environment in which the vehicle will travel. For large outdoor areas, this corresponds to a slice at a constant altitude of a digital surface model (DSM) made with a LIDAR, and for smaller scale scenes, it is simply a digital photograph. The proposed algorithm processes these data in the form of matrices of pixels: the pixels within the same obstacle have the same constant positive value and the pixels of free space have the value zero. The shortest paths calculations can be performed either at a ground station or in the moving vehicle if the latter has enough calculating power. Once the shortest path is calculated, the vehicle is simply provided with the sequence positions that corresponds to the pixels in this path, and sent on its way. In order to follow this path, the vehicle then only needs a positioning system. This could be a GPS receiver if it moves in large outside areas, as in the examples shown at the end of this article, or any of the interior positioning systems mentioned in the review [7] if it moves in small areas. It would also be desirable for the vehicle to possess a proximity sensor, as a safety measure that complements the main positioning system, because shortest paths require the vehicle to pass very close to the boundaries of some of the obstacles.