Space Missions Engineering Laboratory
Path Planning Algorithms
The navigation of planetary exploration rover is usually carried on following a path which is computed in order to avoid the individuated obstacles and which allows to reach the target. In autonomous rover this step is executed by algorithms on board the rover, based on the information gathered by the vision system. The research carried on in our group in this field is aimed at designing fast and reliable path planning algorithms which allows both the obstacle avoidance, the minimization of the energy consumption and the maximization of the reliability of the trajectory.
The problem of path planning is strictly connected with the representation of the environment that can be generated using the information provided by the vision system. In particular three different approach has been analysed:
- a Priori path planning on 2D maps;
- a Priori path planning on 3D maps;
- real-time path planning on 2D maps.
The A Priori path planning algorithm developed for the 2D map case is fast and cheap in terms of computational resources, however the path is identified only avoiding obstacles and minimizing the length. The algorithm developed is based on the A-Star algorithm which is optimized for the solution of planar problem.
In the case of 3D maps, the algorithm developed is able to identify a path that avoids obstacles but also with a minimization of the overall risk associated with the studied trajectory. This is achieved considering not only the presence of possible obstacles but also by evaluating the so-called traversability condition of each point of the trajectory. In this way the path is computed considering all the available information on the environment and the geometrical constraint imposed by the rover configuration, but it is considerably more expensive in terms of computational burden. The developed algorithm treats the problem as a constrained optimization solved with a Simulated Annealing algorithm which exploits a stochastic search technique to find the minimum of an objective function.
In the case of real time path planning the trajectory is computed step by step reacting to the environment. The approach used for this kind of problem is based on the Artificial Potential Field theory in which obstacles are associated with repulsive field while target is associated with attractive field. The manoeuvres are generated step by step, considering the local value of the overall potential field. This approach is fast and reliable and allows to better face uncertainties in the reconstruction of the environment as a new individuated obstacles can be introduced as a new repulsive field and the computed path instantly take into consideration the new information. However this approach does not allow to compute an optimal overall trajectory, as in the case of a priori path planning, because it is based only on local information.
Powered by CMSimple