Computational motion planning in planar space
This application enables pathfinding in planar 2D space from point A to point B, taking into account obstacles and the robot's shape. It supports multiple pathfinding algorithms, allowing users to explore different approaches to solving the motion planning problem.
Main features:
- Planar 2D pathfinding
- Custom-shaped robot support
- Dynamic obstacle handling
- Multiple pathfinding algorithms for comparison
- Area scanning in unknown environment
- Visualization of intermediate steps for better understanding
Originally developed as part of a diploma project, this tool is ideal for studying or teaching motion planning and related algorithms.
Project uses vcpkg package manager and CMake.
Quick Visual Studio project generation steps:
cmake . -B build -DCMAKE_TOOLCHAIN_FILE=path/to/vcpkg/scripts/buildsystems/vcpkg.cmake
The application uses the Minkowski sum to compute the configuration space, determining the allowed positions where the robot can be placed. This method accounts for both the robot's shape and the obstacles in the environment, ensuring accurate pathfinding in complex scenarios.
The app supports multiple pathfinding algorithms, allowing users to explore different approaches to motion planning:
- RRT (Rapidly-exploring Random Tree) for probabilistic path exploration.
- Visibility Graph for constructing optimal paths through free space by connecting visible vertices.
- Voronoi Map to plan paths while maximizing distance from obstacles.
A graph structure is used to store preprocessed maps when utilizing the Visibility Graph or Voronoi Map algorithms, optimizing performance during repeated path calculations.
Dijkstra's algorithm is utilized to efficiently search for the shortest path in a graph, ensuring optimal routing.
The application features a user-friendly graphical interface built using the Qt framework, making it easy to interact with various tools and visualizations for motion planning.
The "state" design pattern is implemented to manage multiple UI workflows, such as:
- Creating and placing objects
- Reshaping the robot
- Dragging the robot across the workspace
The app introduces a file format for saving and loading scenes, enabling users to store and retrieve their work efficiently.
The application can generate random obstacle maps, including labyrinth-like structures, allowing for extensive testing and experimentation with different environments.
An experimental algorithm is included for robot navigation in unknown environments, simulating real-world scenarios where obstacles are discovered during movement.
