Path Diversity Is Only Part of the Problem

Abstract

The goal of motion planning is to find a feasible path that connects two positions and is free from collision with obstacles. Path sets are a robust approach to this problem in the face of real-world complexity and uncertainty. A path set is a collection of feasible paths and their corresponding control sequences. A path-set-based planner navigates by repeatedly testing each of these robot-fixed paths for collision with obstacles. A heuristic function selects which of the surviving paths to follow next. At each step, the robot follows a small piece of each path selected while simultaneously planning the subsequent trajectory. A path set possesses high path diversity if it performs well at obstacle-avoidance and goal-seeking behaviors. Previous work in path diversity has tacitly assumed that a correlation exists between this dynamic planning problem and a simpler, static path diversity problem: a robot placed randomly into an obstacle field evaluates its path set for collision a single time before following the chosen path in entirety. Although these problems might intuitively appear to be linked, this paper shows that static and dynamic path diversity are two distinct properties. After empirically demonstrating this fact, we discuss some of the factors that differentiate the two problems.