Homotopy-Aware RRT*: Toward Human-Robot Topological Path-Planning

Abstract

An important problem in human-robot interaction is for a human to be able to tell the robot to a particular location with instructions on how to get there or what to avoid on the way. This paper provides a solution to problems where the human wants the robot not only to optimize some objective but also to honor soft or hard topological constraints, i.e. go quickly from A to B while avoiding C. The paper presents the HARRT* (homotopy-aware RRT*) algorithm, which is a computationally scalable algorithm that a robot can use to plan optimal paths subject to the information provided by the human. The paper provides a theoretic justification for the key property of the algorithm, proposes a heuristic for RRT*, and uses a set of simulation case studies of the resulting algorithm to make a case for why these properties are compatible with the requirements of human-robot interactive path-planning.