# Lazy Probabilistic Roadmaps Revisited

arXiv: https://arxiv.org/abs/2209.14471 · HTML: https://mlsanity.com/paper/2209.14471/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 54 references that are in the map.
- First posted on arXiv 28 Sep 2022.

## Builds on (most cited first, 8 of 8)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Control Barrier Functions: Theory and Applications](https://mlsanity.com/paper/1903.11199/) (2019)
- [Benchmarking Metric Ground Navigation](https://mlsanity.com/paper/2008.13315/) (2020)
- [Kinodynamic Motion Planning: A Novel Type Of Nonlinear, Passive Damping Forces And Advantages](https://mlsanity.com/paper/1606.09270/) (2016)
- [Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance](https://mlsanity.com/paper/1505.00023/) (2015)
- [Revisiting the Asymptotic Optimality of RRT^*](https://mlsanity.com/paper/1909.09688/) (2019)
- [The Critical Radius in Sampling-based Motion Planning](https://mlsanity.com/paper/1709.06290/) (2017)
- [Sampling Polynomial Trajectories for LTL Verification](https://mlsanity.com/paper/2104.08980/) (2021)

## Abstract (arXiv)

This paper describes a revision of the classic Lazy Probabilistic Roadmaps algorithm (Lazy PRM), that results from pairing PRM and a novel Branch-and-Cut (BC) algorithm. Cuts are dynamically generated constraints that are imposed on minimum cost paths over the geometric graphs selected by PRM. Cuts eliminate paths that cannot be mapped into smooth plans that satisfy suitably defined kinematic constraints. We generate candidate smooth plans by fitting splines to vertices in minimum-cost path. Plans are validated with a recently proposed algorithm that maps them into finite traces, without need to choose a fixed discretization step. Trace elements exactly describe when plans cross constraint boundaries modulo arithmetic precision. We evaluate several planners using our methods over the recently proposed BARN benchmark, and we report evidence of the scalability of our approach.