Abstract

We reformulate the classic Lazy Probabilistic Roadmaps algorithm (Lazy PRM) for robot motion planning as a Branch-and-Cut procedure for infinite mathematical programming problems. Specifically, the set of decision variables - points in a suitably defined configuration space - is infinite. Such problems are only feasible if some form of problem approximation is adopted. Interestingly, this approximation is performed automatically and integrated within several other constraint reasoning components built around concepts in Graph and Number Theory. Still, the resulting problem results in a polynomial programming problem, for which the state-of-the-art approach solves relaxations and utilizes their solutions as proxies for actual ones.

Our revised Lazy PRM procedure searches for plans (smooth trajectories in configuration space) that satisfy given constraints of geometric (collision avoidance) and differential (velocity limits) nature. We obtain candidate plans by fitting Hermitian splines to vertices selected by minimum-cost paths in a finite sub-graph covering configuration space. Satisfaction of constraints is then determined exactly, modulo available arithmetic precision, by a novel algorithm that maps smooth curve segments into a finite trace, each word in the trace a conjunction of logical propositions encoding whether the curve segment crosses the boundary of a constraint. These traces can then be used to certify that suitably designed control algorithms can track the plans without the robot colliding with obstacles or engaging in maneuvers that cannot be executed in the physical world.

We evaluate several planners using our proposed methods over the recently proposed BARN benchmark for robot motion planning and obtain empirical evidence of our approach's feasibility and scalability.