Informative path planning with a human path constraint

One way for a human and a robot to collaborate on a search task is for the human to specify constraints on the robot´s path and then allow the robot to find an optimal path subject to these constraints. This paper presents an anytime solution to the robot´s path-planning problem when the human specifies a path constraint and an acceptable amount of deviation from this path. The robot´s objective is to maximize information gathered during the search subject to this constraint. We first discretize the path constraint and then convert the resulting problem into a multi-partite graph. Information maximization becomes a submodular orienteering problem on this topology structure. Backtracking is used to generate an efficient heuristic for solving this problem, and an expanding tree is used to facilitate an anytime algorithm.