Adaptive Path Planning Using Depth-First Search in Environments with Dynamic Obstacle

Abstract

Depth-First Search (DFS) is one of the classical algorithms used for robotic path planning due to its simplicity and deterministic exploration strategy. However, its performance can degrade significantly in environments where obstacles move or appear unexpectedly. This study analyzes the behavior of the DFS algorithm under both static and dynamic obstacle conditions using a grid-based simulation. Three primary performance indicators were evaluated: total path length, turning complexity, and overall path efficiency. In static environments, where all obstacle positions were known beforehand, DFS demonstrated stable and efficient navigation, achieving approximately 117% shorter paths, 42% higher efficiency, and 133% fewer turning maneuvers compared to scenarios with dynamic obstacles. When unexpected obstacles were introduced, the robot frequently performed backtracking and route replanning, which increased the total travel distance and the number of directional changes, ultimately lowering navigation efficiency. Despite these challenges, the DFS algorithm was still capable of reaching the goal after multiple replanning steps. These findings highlight both the robustness and limitations of DFS and suggest that integrating adaptive sensing or hybrid algorithms could improve performance in unpredictable, dynamic environments.