A* Algorithm

A* is an informed search algorithm, meaning it uses a heuristic function to estimate the cost to the goal. This guides its exploration, making it far more efficient than uninformed searches like Breadth-First Search (BFS) or Depth-First Search (DFS). It expands the most promising node first, based on the sum of the cost to reach the node and the estimated cost to the goal.

• Core Mechanism: It maintains a priority queue (the open set) sorted by the total estimated cost f(n) = g(n) + h(n).
• Efficiency: By focusing search effort towards the goal, it typically evaluates far fewer nodes than Dijkstra's algorithm, which explores equally in all directions.

The algorithm's decision-making is governed by a cost function f(n) for each node n.

• g(n) (Path Cost): The exact, known cost from the start node to node n. This accumulates real traversal costs (e.g., distance, time).
• h(n) (Heuristic): An admissible heuristic function that estimates the cost from node n to the goal. Common heuristics include Euclidean distance (for flying distance) or Manhattan distance (for grid movement).
• f(n) (Total Estimated Cost): The sum g(n) + h(n). This is the estimated total cost of the path from start to goal that goes through node n. The node with the lowest f(n) is always expanded next.

For A* to be optimal (guarantee the shortest path), its heuristic h(n) must meet specific criteria.

• Admissible Heuristic: The heuristic must never overestimate the true cost to reach the goal. It must be optimistic. h(n) ≤ h*(n) where h*(n) is the true cost.
• Consistent (Monotonic) Heuristic: A stronger condition where the heuristic estimate from a node to the goal is less than or equal to the cost of moving to a successor plus the heuristic estimate from that successor. Formally: h(n) ≤ c(n, n') + h(n'). Consistency implies admissibility and ensures the algorithm finds the optimal path without needing to re-evaluate nodes.
• Example: In a 2D grid, the Manhattan distance is admissible and consistent if the robot can only move up, down, left, or right.

A* provides strong theoretical guarantees under the right conditions.

• Completeness: A* is complete on finite graphs with a finite branching factor. It will always find a solution if one exists, as it systematically explores all possible paths (guided by the heuristic).
• Optimality: When using an admissible heuristic, A* is guaranteed to find the least-cost path from the start to the goal. This makes it the algorithm of choice for applications where optimality is critical, such as robotics navigation or game AI for strategic pathfinding.
• Trade-off: The more accurate the heuristic (closer to the true cost without overestimating), the fewer nodes A* will expand, making it more efficient.

A* manages its search frontier and explored nodes using two primary data structures.

• Open Set (Frontier): Typically a priority queue (e.g., a min-heap) containing nodes scheduled to be evaluated. Nodes are ordered by their f(n) score. The node with the lowest f(n) is popped for expansion.
• Closed Set (Explored): A set (e.g., a hash table) containing nodes that have already been expanded. This prevents the algorithm from re-evaluating nodes and entering infinite loops.
• Process: When a node is expanded, it is moved from the open set to the closed set. Its neighbors are generated; if a neighbor is not in the closed set and has a better g(n) cost than a previous visit, it is added/updated in the open set.

In Task and Motion Planning (TAMP), A* is often used at the geometric or kinematic planning level.

• Discretized State Spaces: The robot's configuration space (C-space) is discretized into a graph (a grid or lattice). A* searches this graph for a collision-free path.
• Heuristic Design: Effective heuristics are crucial. For a mobile robot, Euclidean distance to the goal is common. For a manipulator, a heuristic might be the Euclidean distance of the end-effector.
• Integration with High-Level Planning: A* solves the low-level motion planning or path planning subproblem. A high-level task planner (e.g., using HTNs or PDDL) might call A* repeatedly to check the feasibility of moving between different symbolic states.
• Example: A high-level plan says "go to the kitchen." A* is used to compute the detailed, collision-free wheeled navigation path through the building.

A* is the canonical heuristic search algorithm. This broader class includes any algorithm that uses an estimated cost-to-goal function h(n) to guide exploration of a state space more efficiently than uninformed methods like breadth-first search.

• Informed Search: Uses domain knowledge via the heuristic.
• Admissible Heuristic: A key requirement for A*'s optimality; it must never overestimate the true cost to the goal.
• Consistent (Monotonic) Heuristic: Ensures the heuristic estimate from a node to the goal is less than or equal to the cost to a successor plus the heuristic from that successor, guaranteeing A* finds an optimal path without re-expanding nodes.

The Configuration Space (C-Space) is the abstract mathematical space where A* and other motion planners typically operate. Every possible pose of a robot is mapped to a single point, and physical obstacles become forbidden regions (C_obs).

• Dimensionality: Defined by the robot's degrees of freedom (e.g., (x, y, θ) for a mobile base).
• State Space vs. C-Space: In planning, state space can include C-Space plus other variables like velocity or battery level.
• Planning in C-Space: A* searches a discretized graph representation of the free space (C_free), finding a path of connected, collision-free configurations.

Hierarchical Task Networks (HTNs) represent a high-level planning formalism often used above A*. While A* finds geometric paths, HTNs decompose abstract tasks into executable actions.

• Task Decomposition: Uses a library of methods to recursively break down compound tasks into primitive actions.
• Integration with Motion Planning: The output primitive action (e.g., "Navigate to Point A") becomes the goal for a low-level planner like A*.
• Symbolic vs. Geometric: HTNs operate on symbolic world states; A* operates on geometric C-Space, illustrating the classic hierarchy in Task and Motion Planning (TAMP).

RRT is a prominent sampling-based planning algorithm, often contrasted with A*. It is designed for high-dimensional C-Spaces where constructing a full graph for A* is intractable.

• Probabilistic Completeness: Guarantees a solution will be found if one exists, as the number of samples approaches infinity.
• No Heuristic Required: Explores space by randomly sampling and extending a tree, making it effective for problems where a good heuristic is unknown.
• Use Case: Preferred for complex manipulator arms (7+ DOF), while A* is often used for 2D or 3D grid-based navigation.

Trajectory Optimization computes a smooth, time-parameterized path that minimizes a cost function (e.g., energy, jerk). It often refines the discrete waypoints produced by a pathfinder like A*.

• From Path to Trajectory: A* produces a sequence of states. Trajectory optimization adds timing, velocity, and acceleration profiles.
• Model Predictive Control (MPC): A receding-horizon form of online trajectory optimization used for dynamic control.
• Dynamics-Aware: Considers the robot's physical dynamics and actuator limits, which pure geometric planners like A* ignore.

PDDL is the standard formal language for defining classical planning problems. It specifies predicates, actions, objects, and initial/goal states for symbolic planners, which can generate high-level action sequences for a robot.

• Symbolic Abstraction: Represents the world in terms of logical facts (e.g., (at robot room1)).
• Planner Output: A PDDL planner's output (a sequence of actions) defines the task plan. Each action requiring movement (e.g., (move room1 room2)) invokes a motion planner like A*.
• STRIPS: PDDL is based on the STRIPS representation, which defines actions by their preconditions and effects.