Graph Theory Algorithms in Robot Path Planning
(Beyond basic BFS / DFS)
Dijkstra's Algorithm
- Finds shortest path from one node to all other nodes by expanding the least-cost node first
- Guarantees optimal path but explores a lot of nodes so it is slow for large maps
- Used as base for grid based planners when heuristic is not available
- Applied in warehouse robots, indoor mobile robots with known static maps
A* (A-Star)
- Dijkstra plus a heuristic function so it expands fewer nodes and reaches goal faster
- Optimal if heuristic is admissible, very commonly used as default global planner
- Works on grid maps, graphs, or lattice representations of the environment
- Applied in ROS2 nav2 global planner, drone waypoint planning, game AI style navigation
D* (Dynamic A*)
- Like A* but built for environments that change, replans only the affected part of path
- Maintains a cost graph and repairs it instead of solving from scratch every time
- Much faster than repeated A* when obstacles appear or move
- Applied in outdoor rovers, Mars rover navigation, unknown/partially known terrain robots
D* Lite
- Simplified reimplementation of D* using LPA* concepts, easier to code and maintain
- Plans backward from goal to start so replanning after new sensor data is cheap
- Very popular in real time robotics because of low replanning cost
- Applied in autonomous ground vehicles, UGVs in defense recon, dynamic obstacle avoidance
Lifelong Planning A* (LPA*)
- Incremental version of A* that reuses previous search info when small changes happen in graph
- Basis on which D* Lite is built
- Good when environment changes slightly and full re-planning is wasteful
- Applied in robots operating in semi dynamic environments like factories with moving racks
Theta*
- Variant of A* that allows any-angle movement instead of only grid aligned moves
- Produces shorter, more realistic and smoother paths than normal grid A*
- Checks line of sight between nodes to skip unnecessary grid points
- Applied in UAV path planning, mobile robots needing smooth trajectories
Hybrid A*
- A* extended with vehicle kinematics so path respects turning radius and vehicle constraints
- Produces continuous, drivable paths instead of just grid connected nodes
- Commonly combined with a cost map from sensors
- Applied in self driving cars, ackermann steering robots, parking maneuver planning
RRT (Rapidly-exploring Random Tree)
- Builds a tree by randomly sampling free space and connecting nearest tree node to sample
- Good for high dimensional spaces like robot arms, not guaranteed optimal
- Fast to find a feasible path even in complex or unknown spaces
- Applied in robotic arm motion planning, drones, humanoid limb planning
RRT*
- RRT with a rewiring step that improves path cost as more samples are added
- Converges to optimal path given enough time/samples unlike plain RRT
- Still probabilistic so run time is not fixed
- Applied in autonomous vehicle planning, manipulator planning, cluttered environments
PRM (Probabilistic Roadmap)
- Randomly samples points in free space and connects nearby points to build a roadmap graph
- Roadmap is built once and reused for multiple queries, good for static environments
- After roadmap is built, normal graph search like A* or Dijkstra is run on it
- Applied in robotic arm planning, multi query motion planning in factories
Visibility Graph
- Connects nodes (start, goal, obstacle corners) that have a direct line of sight between them
- Gives shortest path around polygonal obstacles when environment is fully known
- Search like Dijkstra/A* is then run on this graph
- Applied in known indoor maps, simple 2D navigation with polygon obstacles
Voronoi Diagram based Planning
- Generates paths that stay as far as possible from all obstacles using Voronoi edges as graph
- Naturally gives safe, collision avoiding routes
- Graph search run on the Voronoi edges to find shortest safe path
- Applied in corridor navigation, defense perimeter patrol robots, safe route planning
ARA* (Anytime Repairing A*)
- Finds a quick suboptimal path first then keeps improving it if more time is available
- Useful when planning time is limited but a path is needed immediately
- Balances between speed and optimality using inflated heuristic that reduces over time
- Applied in real time robotics with strict time budget, search and rescue robots
CBS (Conflict-Based Search)
- Plans path for each robot separately first, then detects conflicts between robots
- Adds constraints to resolve conflicts and replans only the conflicting robots
- Gives optimal solution for multi robot path planning without huge joint state space
- Applied in warehouse robot fleets, multi robot swarm coordination, drone swarms
M* Algorithm
- Multi robot planner that plans robots independently and only couples robots that conflict
- More scalable than planning in full joint configuration space of all robots
- Dynamically increases coupling only where needed then decouples again
- Applied in multi robot warehouse systems, swarm robotics with limited conflicts
Where These Are Generally Applied
- Global path planning on known maps: Dijkstra, A*, Visibility Graph, Voronoi
- Dynamic/unknown environments needing replanning: D*, D* Lite, LPA*, ARA*
- High dimensional or manipulator planning: RRT, RRT*, PRM
- Vehicle like robots needing smooth/kinematic paths: Hybrid A*, Theta*
- Multi robot/swarm coordination: CBS, M*, decentralized Voronoi partitioning
Project Ideas (ROS2 doable, with novelty)
- Multi Robot Emergency Medical Delivery in Hospital using CBS - fleet of small robots deliver medicines/blood
samples across hospital corridors, CBS resolves conflicts at junctions, novelty is priority based CBS where
critical/emergency robot gets right of way
- D* Lite based Autonomous Casualty Evacuation Robot - UGV navigates disaster/battlefield terrain that changes
due to debris/smoke, replans in real time using D* Lite, novelty is fusing D* Lite with a risk/danger cost map
instead of only distance cost
- RRT* + CBS Hybrid Search and Rescue Swarm - multiple small robots explore rubble using RRT* for local
unknown space and CBS for coordinating shared corridors, novelty is switching planner type based on how explored
the environment is
- Decentralized Voronoi based Perimeter Surveillance for Defense - swarm of ground robots patrol a perimeter using
Voronoi partitioning so each robot covers its own region, novelty is dynamic re-partitioning when a robot is
lost/disabled simulating combat attrition
- Priority based Multi Robot Ambulance Fleet Path Planning - simulate multiple medical robots in a city grid, use
CBS or priority planning so higher priority patient case gets fastest conflict free path, novelty is dynamic priority
reassignment based on patient vitals input
- Hybrid A* for Autonomous Supply Robot in Defense Terrain - a rover with car like constraints delivers
ammo/supplies over uneven terrain, novelty is combining Hybrid A* with terrain cost (slope, mud, cover) instead of
plain obstacle map
- UAV-UGV Coordinated Path Planning for Contested Zone - drone builds live obstacle/threat map, ground robot
uses D* Lite to replan path based on that live map, novelty is the UAV-to-UGV cost map sharing pipeline done fully
in ROS2 topics
- All of the above are realistic in ROS2 using Nav2 stack, TurtleBot3/Gazebo simulation, custom planner plugins,
and multi robot namespaces for spawning multiple robots