A simple robot path planning library as illustrated in this figure.
This is a small library that demonstrates a path planning algorithm, with functionality to:
- initialize a map grid
- add circular obstacles to the map
- save the map
- load a saved map
- compute the shortest path given a start and end point
- visualize the path and map together
- Install Python3
- Install dependencies with PIP:
python3 -m pip install matplotlib numpy pillow- For an example of usage, please see example.py in the
pyfolder or simply run the example:
python3 py/example.py- Still a W.I.P.
- Precompute validity mask rather than computing radial distances each time
- Convert binary map to distance-to-nearest-obstacle map for faster computation
- Enable 8-connected traversal by traveling the same distance per step in all directions
- Store map/obstacles as vector graphics instead of PNG
- Change distance step size proportional to image size, not pixels
- Implement Dijkstra or A* instead of the BFS solution for slight speed up
- Convert to C++
-
Performance - What is the bottleneck in your library? How could you go about improving performance in the future?
Current bottlenecks are the pixel-based traversal, repeat radial checking, and over-searching the space. All can be easily improved with a little more time.
-
Modularity - How would you handle additional planning algorithms and new methods of updating the map?
The code is very modular. A new planning algorithm would simply replace the existing function call. The same is true of updating the map.
-
Cross-Platform - How would you alter your library to support multiple Operating Systems or multiple processors with different instruction sets?
The Python version is already cross-platform as I'm using all standard packages. C++ would require a bit more work to compile for specific ISAs, but I don't see it being a major blocker.