Probabilistic Roadmaps sample points in a space, use them to create a graph, and return a path through the graph consisting of completely valid points and edges that have no collisions with obstacles. Traditional roadmaps check the validity of nodes and edges during the graph construction, ensuring that any node or edge in the graph is valid. However, checking the validity of a point or an edge is computationally intensive, and in dynamic environments where nodes and edges are not guaranteed to stay valid forever, a lazy approach to validity checking can save computation time. This project evaluates the performance of 4 algorithms that delay validity checking until the path-planning (Semi-lazy PRM) or path-processing (Fully-lazy PRM, Lazy RRT, Lazy EST) phases, finding that lazy evaluation can have significant benefits in dynamic environments.
See the project report for algorithm overviews and specific results.
- Configure prm_algos_tester_final.py parameters:
- ALL_MAPS - maps to test algorithms on, one map per query
- SHOW_PLOT - set true to see the outcome of each test, false to run tests for numerical results
- DO_ALGO - true if executing the corresponding algorithm, false otherwise
- Algorithm parameters specified at the top (keep consistent for fair testing)
- Run
python3 prm_algos_tester_final.py - Configure mode, METRIC_TO_PLOT and file names, and run
python3 plotter.py
- Overall, Fully-lazy PRM adapts well to dynamic environments and consistently has the fewest validity checks. With the current results, Fully-lazy PRM would be our go to in real dynamic environments.
- In an environment with a large, impeding shape, Semi-lazy PRM narrows down A* options quickly and may outperform Fully-lazy PRM.
- While they have high numbers of validity checks in a static environment, Lazy RRT and Lazy EST learn dynamic environments best, improving the most per query with increasing numbers of queries in realistic, slowly changing environments.
See project report and data visualization video.