# Incremental Sampling-based Algorithm for Minimum-violation Motion Planning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2013.

## Built on by (most cited first, 9 of 9)

- [Parallel and Multi-Objective Falsification with Scenic and VerifAI](https://mlsanity.com/paper/2107.04164/) (2021)
- [Computational Tradeoff in Minimum Obstacle Displacement Planning for Robot Navigation](https://mlsanity.com/paper/2302.07114/) (2023)
- [Traffic-Rule-Compliant Trajectory Repair via Satisfiability Modulo Theories and Reachability Analysis](https://mlsanity.com/paper/2412.15837/) (2024)
- [Locally Optimal Solutions to Constraint Displacement Problems via Path-Obstacle Overlaps](https://mlsanity.com/paper/2511.12203/) (2025)
- [Incorporating System-level Safety Requirements in Perception Models via Reinforcement Learning](https://mlsanity.com/paper/2412.02951/) (2024)
- [SuReNav: Superpixel Graph-based Constraint Relaxation for Navigation in Over-constrained Environments](https://mlsanity.com/paper/2602.06807/) (2026)
- [Legislating World-Model-Based Planning with Legal Reasoning](https://mlsanity.com/paper/2609.15113/) (2026)
- [Commonsense-Grounded Path Planning from Abstract Instructions](https://mlsanity.com/paper/2609.22813/) (2026)
- [A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation](https://mlsanity.com/paper/2609.22974/) (2026)

## Abstract (arXiv)

This paper studies the problem of control strategy synthesis for dynamical systems with differential constraints to fulfill a given reachability goal while satisfying a set of safety rules. Particular attention is devoted to goals that become feasible only if a subset of the safety rules are violated. The proposed algorithm computes a control law, that minimizes the level of unsafety while the desired goal is guaranteed to be reached. This problem is motivated by an autonomous car navigating an urban environment while following rules of the road such as "always travel in right lane'' and "do not change lanes frequently''. Ideas behind sampling based motion-planning algorithms, such as Probabilistic Road Maps (PRMs) and Rapidly-exploring Random Trees (RRTs), are employed to incrementally construct a finite concretization of the dynamics as a durational Kripke structure. In conjunction with this, a weighted finite automaton that captures the safety rules is used in order to find an optimal trajectory that minimizes the violation of safety rules. We prove that the proposed algorithm guarantees asymptotic optimality, i.e., almost-sure convergence to optimal solutions. We present results of simulation experiments and an implementation on an autonomous urban mobility-on-demand system.