Title :
Risky planning: Path planning over costmaps with a probabilistically bounded speed-accuracy tradeoff
Author :
Murphy, Liz ; Newman, Paul
Author_Institution :
Sch. of Eng. Syst., Queensland Univ. of Technol., Brisbane, QLD, Australia
Abstract :
This paper is about generating plans over uncertain maps quickly. Our approach combines the ALT (A* search, landmarks and the triangle inequality) algorithm and risk heuristics to guide search over probabilistic cost maps. We build on previous work which generates probabilistic cost maps from aerial imagery and use these cost maps to precompute heuristics for searches such as A* and D* using the ALT technique. The resulting heuristics are probability distributions. We can speed up and direct search by characterising the risk we are prepared to take in gaining search efficiency while sacrificing optimal path length. Results are shown which demonstrate that ALT provides a good approximation to the true distribution of the heuristic, and which show efficiency increases in excess of 70% over normal heuristic search methods.
Keywords :
aerospace robotics; path planning; statistical distributions; ALT algorithm; aerial imagery; guide search; normal heuristic search methods; path planning; probabilistic cost maps; probability distributions; risk heuristics; Approximation methods; Heuristic algorithms; Path planning; Planning; Probabilistic logic; Probability distribution; Robots;
Conference_Titel :
Robotics and Automation (ICRA), 2011 IEEE International Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-386-5
DOI :
10.1109/ICRA.2011.5980124