Motion planning lies at the core of autonomous robotics, enabling systems to determine feasible, efficient, and safe paths in complex environments. At the advanced level, this task involves integrating geometry, probability, optimization, and dynamics into a coherent framework that allows intelligent agents to navigate uncertain, dynamic worlds. This chapter explores foundational and cutting-edge techniques in robot motion planning, including deterministic search, sampling-based strategies, trajectory optimization, dynamic obstacle avoidance, and real-time planning in unknown environments.

A Algorithm (Graph-Based Deterministic Planning)
A is a best-first search algorithm that uses cost-to-come (g(n)) and cost-to-go (h(n)) to explore the space: f(n)=g(n)+h(n)
● Admissibility: If h(n) never overestimates the true cost, A guarantees optimality.
● Complexity: Exponential in worst-case; mitigated via heuristics.
● Limitations: Struggles with high-dimensional or continuous spaces.
A is fundamental to many embedded path planners in discrete environments, such as mobile robot grid maps or roadmap navigation in automated warehouses.

D and D Lite
D (Dynamic A) extends A to accommodate changing environments. It efficiently updates the existing plan as new information (e.g., obstacles) becomes available. This is especially useful in semi-structured outdoor navigation, planetary rovers, and autonomous vehicles where the map is incomplete or dynamic. D Lite is a simplified version with reduced overhead and is widely used in mobile robotics. It builds on the concept of incremental search, reducing the need to replan from scratch.

As the dimensionality of the robot's configuration space increases, deterministic methods become infeasible. Sampling-based planners are designed to address these challenges by probabilistically exploring the space. Rapidly-Exploring Random Tree (RRT) RRT is designed for pathfinding in high-dimensional continuous spaces. The algorithm incrementally builds a tree rooted at the start configuration:
● Randomly samples a point in the configuration space
● Connects the nearest tree node to the sample if the motion is collision-free
● Repeats until the goal is reached or a time limit is exceeded
⚠ RRT does not guarantee optimality. It excels in fast, feasible pathfinding for systems like UAVs and robotic arms with many joints.

Motion planning must not only find a collision-free path but also generate a trajectory that respects dynamics, kinematic constraints, and task goals. Objective
Given a path {x0,x1,…,xn}, find a trajectory that minimizes:
J=∑i=1n(∥xi−xi−1∥2+λ⋅C(xi))
Where:
● ∥xi−xi−1∥: smoothness
● C(xi): collision cost
● λ: weighting factor
Common Optimization Methods
● CHOMP (Covariant Hamiltonian Optimization): Gradient-based method optimizing trajectories in continuous space.
● TrajOpt: Uses sequential convex optimization with collision checking.
● STOMP (Stochastic Trajectory Optimization): Samples noisy trajectories and uses cost weighting to refine paths.

Robots in real environments must handle moving obstacles — humans, vehicles, animals, or other robots — in non-deterministic ways.
Approaches
Velocity Obstacle (VO) Calculates the set of robot velocities that will result in a future collision and avoids them. Mathematically, the VO is: VOA∣B={vA∣∃t>0:pA+vAt=pB+vBt}
Used extensively in swarm robotics and mobile robot navigation in shared spaces. Dynamic Window Approach (DWA) Instead of searching in configuration space, DWA samples velocities and chooses the one that:
● Avoids obstacles
● Progresses toward the goal
● Respects dynamic limits
Artificial Potential Fields (APF)
● Goal: Attractive force
● Obstacles: Repulsive force
While intuitive, APFs can suffer from local minima, making them unsuitable for complex maps unless combined with global planners.

In many applications (e.g., autonomous exploration, disaster robotics), the robot must plan in partially or completely unknown environments.
Techniques
Frontier-Based Exploration detects boundaries between known and unknown areas and directs motion toward them. Widely used in SLAM-enabled systems. Incremental Replanning combines mapping (e.g., with LiDAR or visual SLAM) with planning:
● Continuously updates local and global maps
● Replans as new data becomes available
● Uses D, LPA, or other incremental algorithms
Hierarchical Planning
● High-level Planner: Handles symbolic goals and long-term paths
● Mid-level Planner: Manages terrain-aware planning
● Low-level Planner: Handles actuation, obstacle avoidance
This decoupling is essential for managing complexity in autonomous driving, robotic mining, and drone delivery.

Learning-Based Planning: Integrating neural networks to guide sampling or learn cost functions (e.g., Neural RRT). Multi-Agent Path Planning (MAPF): Coordinated planning in robot fleets (e.g., warehouse swarms). Hybrid Planning: Combining symbolic reasoning with geometric motion planning (e.g., Task and Motion Planning - TAMP). Risk-Aware Planning: Probabilistic motion planning under uncertainty, accounting for stochastic disturbances and model errors.