A Deep Dive into Static and Dynamic
Pathfinding for TurtleBot4

2026 Senior Capstone Project — Carleton College

Project Overview

This project explores obstacle avoidance and autonomous navigation on the TurtleBot4 robotic platform using Robot Operating System 2 (ROS 2). We implement, tune, and compare five distinct navigation algorithms — ranging from classical graph-search planners to reactive local controllers — to understand their trade-offs in real-world and simulated environments.


Each algorithm was tested in the Gazebo simulator and on a physical TurtleBot4, navigating custom maze-style environments. We evaluate performance across metrics including path optimality, computation time, obstacle clearance, and robustness to dynamic obstacles.


The stack is built on ROS 2 Jazzy / Humble, leveraging Nav2, AMCL localization, SLAM Toolbox, and TF2. All algorithm source code is available in our GitHub repository.

Algorithms

Five navigation approaches — two global planners, one dynamic replanner, one reactive controller, and a hybrid stack.

Global Planner

A* (A-Star)

A* is a heuristic-guided graph search algorithm that finds the shortest path from a start to a goal on a 2D occupancy grid. It combines the cost-to-reach (g) with an admissible heuristic estimate (h) to efficiently prioritize promising nodes.

  • Optimal path on uniform-cost grids
  • Euclidean heuristic for grid navigation
  • Hybrid obstacle inflation for safety margins
  • Pure pursuit waypoint following
  • Standalone or planner-only mode (for stacking with DWA)
Dynamic Replanner

D* Lite

D* Lite is an incremental heuristic search algorithm derived from Lifelong Planning A*. It searches backwards from the goal, enabling efficient replanning when new obstacles are detected — ideal for partially-known or changing environments.

  • Incremental replanning without full recomputation
  • SLAM integration for map updates
  • LiDAR-based dynamic obstacle detection
  • Automatic replanning on obstacle discovery
  • Real-time path visualization
Global Planner

Jump Point Search (JPS)

Jump Point Search is an optimization of A* for uniform-cost grids. It dramatically reduces the node expansion count by identifying and skipping symmetrical paths, jumping directly to "jump points" that are guaranteed to be on optimal paths.

  • Significantly faster than standard A* on open grids
  • Same optimal path guarantees as A*
  • Forced neighbor pruning rules
  • Interactive goal input via terminal
  • Real-time visualizer for jump point expansion
Reactive Controller

DWA (Dynamic Window Approach)

The Dynamic Window Approach is a reactive local planner that samples the robot's velocity space within a kinematically-feasible window, simulates candidate trajectories, and selects the trajectory with the best combined cost score.

  • Real-time local obstacle avoidance
  • Configurable cost weights (goal, obstacle, velocity, smoothness)
  • Emergency stop on critical proximity
  • TF2/AMCL localization integration
  • Standalone or local-controller mode (stacked with A*)
Hybrid Stack

Hybrid A* + DWA

The hybrid approach combines A* as a global planner with DWA as a local controller, mirroring the Nav2 planner/controller architecture. A* computes the optimal global path; DWA executes it in real time while avoiding obstacles.

  • Global optimality from A* path planning
  • Real-time obstacle reactivity from DWA
  • Path-tracking cost terms guide DWA along A* plan
  • Lookahead carrot-following for smooth execution
  • Mirrors ROS 2 Nav2 planner/controller split