Path Planning for a Tethered Robot Using Multi-Heuristic A* with Topology-Based Heuristics

September 2015

Path Planning for a Tethered Robot Using Multi-Heuristic A* with Topology-Based Heuristics

Authors:

Soonkyum Kim and Maxim Likhachev
Conference Paper
Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems

Abstract:

In this paper, we solve the path planning problem for a tethered mobile robot, which is connected to a fixed base by a cable of length L. The reachable space of the robot is restricted by the length of the cable and obstacles. The reachable space of the tethered robot can be computed by considering the topology class of the cable. However, it is computationally too expensive to compute this space a-priori. Instead, in this paper, we show how we can plan using a recently-developed variant of A* search, called Multi-Heuristic A*. Normally, the Multi-Heuristic A* algorithm takes in a fixed set of heuristic functions. In our problem, however, the heuristics represent length of paths to the goal along different topology classes, and there can be too many of them and not all the topology classes are useful. To deal with this, we adapt Multi-Heuristic A* to work with a dynamically generated set of heuristic functions. It starts out as a normal weighted A*. Whenever the search gets trapped in a local minimum, we find the proper topology class of the path to escape from it and add the corresponding new heuristic function into the set of heuristic functions considered by the search. We present experimental analysis comparing our approach with weighted A* on planning for a tethered robot in simulation.
@conference{Kim-2015-109512,
author = {Soonkyum Kim And Maxim Likhachev},
title = {Path Planning for a Tethered Robot Using Multi-Heuristic A* with Topology-Based Heuristics},
booktitle = {Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2015},
month = {September},
pages = {4656 - 4663},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.