SUT · Robot Path Planning: Potential Fields & Shortest Path

Implemented and compared two foundational autonomous robot path planning algorithms in MATLAB for 2D environments with multiple line-segment obstacles, developed as coursework in the Robotics curriculum at Sharif University of Technology. Both methods address the core challenge of collision-free navigation from a start configuration to a goal in cluttered workspaces.

The first method, Artificial Potential Field (APF), models the goal as an attractive potential and each obstacle as a repulsive field. A custom path_generator function iterates with convergence threshold ε = 0.1, computing at each step the attractive force Fatt toward the target and the repulsive force Frep per obstacle via parametric closest-point computation on line segments (three-region case analysis with Cramer's rule intersection). All contributions are summed into a resultant Fd vector and the robot advances by step ε. Two environments were analyzed: a clear-path scenario demonstrating successful goal convergence, and a deliberately constructed local minimum trap in which the robot oscillates indefinitely between two points — providing a controlled characterization of APF's fundamental limitation.

The second method, Visibility Graph + Dijkstra's Shortest Path, constructs a graph of all collision-free point-to-point connections by testing each candidate segment against all obstacles using parametric intersection detection (α, β ∈ [0,1] as the collision criterion). Valid edges are stored with their Euclidean length as edge weight in a matrix. Dijkstra's algorithm is then applied from the goal node backward, greedily relaxing distances through unvisited neighbors until the globally shortest collision-free path is recovered. The optimal path is visualized in MATLAB with valid graph edges in green and the shortest path in red.