Category Archives: Robot Motion Planning

Taking into account the way a path serves to avoid obstacles in order to improve the three main methods of robot path planning: graph-search, probabilistic and bug

December 19, 2014 10:17 ,

Emili Hernandez, Marc Carreras, Pere Ridao, A comparison of homotopic path planning algorithms for robotic applications , Robotics and Autonomous Systems, Volume 64, February 2015, Pages 44-58, ISSN 0921-8890, DOI: 10.1016/j.robot.2014.10.021

.

This paper addresses the path planning problem for robotic applications using homotopy classes. These classes provide a topological description of how paths avoid obstacles, which is an added value to the path planning problem. Homotopy classes are generated and sorted according to a lower bound heuristic estimator using a method we developed. Then, the classes are used to constrain and guide path planning algorithms. Three different path planners are presented and compared: a graph-search algorithm called Homotopic A∗ (HA∗), a probabilistic sample-based algorithm called Homotopic RRT (HRRT), and a bug-based algorithm called Homotopic Bug (HBug). Our method has been tested in simulation and in an underwater bathymetric map to compute the trajectory of an Autonomous Underwater Vehicle (AUV). A comparison with well-known path planning algorithms has also been included. Results show that our homotopic path planners improve the quality of the solutions of their respective non-homotopic versions with similar computation time while keeping the topological constraints.

Posted in: Robot motion planning , Tagged:

A good summary and classification of state-of-the-art motion planning algorithms and proposal of a new one that improve the expected computational cost

December 9, 2014 17:23 ,

Rickert, M.; Sieverling, A.; Brock, O., Balancing Exploration and Exploitation in Sampling-Based Motion Planning, Robotics, IEEE Transactions on , vol.30, no.6, pp.1305,1317, Dec. 2014. DOI: 10.1109/TRO.2014.2340191

We present the exploring/exploiting tree (EET) algorithm for motion planning. The EET planner deliberately trades probabilistic completeness for computational efficiency. This tradeoff enables the EET planner to outperform state-of-the-art sampling-based planners by up to three orders of magnitude. We show that these considerable speedups apply for a variety of challenging real-world motion planning problems. The performance improvements are achieved by leveraging work space information to continuously adjust the sampling behavior of the planner. When the available information captures the planning problem’s inherent structure, the planner’s sampler becomes increasingly exploitative. When the available information is less accurate, the planner automatically compensates by increasing local configuration space exploration. We show that active balancing of exploration and exploitation based on workspace information can be a key ingredient to enabling highly efficient motion planning in practical scenarios.

Posted in: Robot motion planning , Tagged: , ,