Constraint-Free Discretized Manifold-Based Path Planner

Abstract

Autonomous robotic path planning in partially known environments, such as warehouse robotics, deals with static and dynamic constraints. Static constraints include stationary obstacles, robotic and environmental limitations. Dynamic constraints include humans, robots and dis/appearance of anticipated dangers, such as spills. Path planning consists of two steps: First, a path between the source and target is generated. Second, path segments are evaluated for constraint violation. Sampling algorithms trade memory for maximal map representation. Optimization algorithms stagnate at non-optimal solutions. Alternatively, detailed grid-maps view terrain/structure as expensive memory costs. The open problem is thus to represent only constraint-free, navigable regions and generating anticipatory/reactive paths to combat new constraints. To solve this problem, a Constraint-Free Discretized Manifolds-based Path Planner (CFDMPP) is proposed in this paper. The algorithm’s first step focuses on maximizing map knowledge using manifolds. The second uses homology and homotopy classes to compute paths. The former constructs a representation of the navigable space as a manifold, which is free of apriori known constraints. Paths on this manifold are constraint-free and do not have to be explicitly evaluated for constraint violation. The latter handles new constraint knowledge that invalidate the original path. Using homology and homotopy, path classes can be recognized and avoided by tuning a design parameter, resulting in an alternative constraint-free path. Path classes on the discretized constraint-free manifold characterize numerical uniqueness of paths around constraints. This designation is what allows path class characterization, avoidance, and querying of a new path class (multiple classes with tuning), even when constraints are simply anticipatory.