MIT's PRISM algorithm guarantees 100% coverage in constrained robot planning

Researchers from MIT have unveiled PRISM, a probabilistic planning algorithm that tackles one of robotics' hardest problems: guaranteeing reachability in belief spaces under motion uncertainty and constraints. Existing methods rely on sampling to build multi-query belief roadmaps but often fail to cover the space adequately, or use robust control that yields high-cost, indirect paths. PRISM introduces a novel controllability result for state covariance under constraints, enabling it to decompose the problem into separate mean-planning and covariance-shrinking steps. This decomposition allows PRISM to prove finite-time completeness — a guarantee that the algorithm will find a feasible path if one exists — while keeping trajectories efficient.

In head-to-head comparisons against state-of-the-art belief-space planners, PRISM demonstrates dramatic improvements. In easy and medium-difficulty scenarios, it achieves 100% roadmap coverage. Even in the hardest test case, which violates PRISM's coverage assumptions, it still attains 97-100% coverage; all competing methods fall below 45%. Additionally, PRISM's online local optimization step reduces both mean trajectory cost and cost variance. This makes it particularly valuable for autonomous systems that must operate safely in uncertain, cluttered environments — from warehouse robots to self-driving cars — where reliable path planning with performance guarantees is critical.