A summary of fundamental path planning and optimization algorithms for robotics and autonomous systems.

path-planning-algorithms.md

Algorithm	Core Idea (How it chooses the next step/node)	Original Work (Citation)	Key Strengths & Weaknesses	Best Use Case
Discrete/Grid-Based Search
Dijkstra's	Expands the node with the lowest actual cost from the start, g(n).	Dijkstra, E. W. (1959). A note on two problems in connexion with graphs.	Strengths: Simple, guaranteed optimal. Weaknesses: Uninformed search, explores in all directions, slow in large spaces.	Finding the provably shortest path in simple, positively weighted graphs where no heuristic is available.
Greedy Best-First	Expands the node with the lowest estimated cost to the goal, h(n).	Doran, J. E., & Michie, D. (1966). Experiments with the Graph Traverser program.	Strengths: Very fast. Weaknesses: Not optimal, can be easily misled by poor heuristics into long or dead-end paths.	When finding any path quickly is far more important than finding the best path.
A* (A-Star)	Expands the node with the lowest sum of actual cost + estimated cost, g(n) + h(n).	Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths.	Strengths: Optimally efficient; guaranteed optimal while exploring less than Dijkstra. Weaknesses: Memory intensive.	The go-to standard for optimal pathfinding on grids, roadmaps, or other discrete state spaces.
Sampling-Based Search
RRT	Grows a tree by randomly sampling the space and connecting the nearest existing node.	LaValle, S. M. (1998). Rapidly-exploring random trees: A new tool for path planning.	Strengths: Quickly finds a feasible path in high-dimensional spaces without a grid. Weaknesses: Not optimal.	Quickly finding an initial, feasible path in high-dimensional, complex spaces (e.g., robot arm motion).
RRT*	Same as RRT, but also rewires existing tree connections as better, lower-cost paths are discovered.	Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning.	Strengths: Converges toward the optimal path over time. Weaknesses: Slower convergence than RRT.	Finding a high-quality or near-optimal path in complex spaces when more planning time is available.
Optimization-Based Planning
Trajectory Optimization	Formulates planning as a numerical optimization problem, minimizing a cost function subject to constraints.	Betts, J. T. (1998). Survey of numerical methods for trajectory optimization.	Strengths: Produces smooth, dynamically feasible paths. Weaknesses: Prone to local minima; computationally expensive.	Refining a rough path from another planner to be smooth, dynamically aware, and executable by a real robot.
Model Predictive Control (MPC)	Continuously solves a short-horizon trajectory optimization problem online to react to the current state.	Garcia, C. E., Prett, D. M., & Morari, M. (1989). Model predictive control: Theory and practice—a survey.	Strengths: Robust to disturbances and model errors by constantly re-planning. Weaknesses: Computationally demanding.	Real-time control and path following in dynamic or uncertain environments, like autonomous driving or drone flight.