PRM 3D

Problem Statement

Probabilistic Roadmaps (PRM) precompute connectivity of free space and then solve fast graph queries between many start-goal pairs.

Model and Formulation

PRM consists of:

• random free-space samples as graph vertices
• local planner collision checks as graph edges
• shortest-path query over roadmap graph

Practical Notes

• Useful for multi-query scenarios with static maps.
• Node density controls completeness-quality trade-off.
• Local planner choice strongly influences roadmap connectivity.

Implementation and Execution

python -m uav_sim.simulations.path_planning.prm_3d

Evidence

References

• Kavraki et al., Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces (1996)
• Hsu et al., Path Planning in Expansive Configuration Spaces

Related Algorithms

• RRT* 3D
• A* 3D