A* Search

The algorithm's core is the evaluation function f(n), which determines the priority of exploring a node n. It is the sum of two components:

• g(n): The exact, known cost from the start node to node n. This accumulates the actual path cost.
• h(n): The heuristic function, which estimates the cost from node n to the goal. This guides the search toward the target. By minimizing f(n), A* balances exploring paths that are already cheap (g(n)) with the promise of being close to the goal (h(n)).

An admissible heuristic is one that never overestimates the true cost to reach the goal. This property is critical because it guarantees that A* will find the shortest possible path. If h(n) is admissible, the first time A* expands the goal node, the path discovered is guaranteed to be optimal.

Example: In a grid, the straight-line (Euclidean) or Manhattan distance to the goal is admissible, as it's the shortest possible distance without obstacles.

A stronger property than admissibility is consistency (or monotonicity). A heuristic is consistent if for every node n and its successor n', the estimated cost from n to the goal is no greater than the cost of moving to n' plus the estimated cost from n' to the goal: h(n) ≤ c(n, n') + h(n').

A consistent heuristic ensures that f(n) is non-decreasing along any path. This means A* finds the optimal path without needing to re-expand nodes, making it more computationally efficient.

A* is implemented as a best-first search using a priority queue (typically a min-heap). The queue, called the open set, stores nodes to be explored, prioritized by their f(n) score.

Process:

1. Start node is added to the open set.
2. The node with the lowest f(n) is popped and expanded.
3. Its neighbors are evaluated (g and f scores calculated) and added to the open set.
4. The algorithm terminates when the goal node is popped from the queue.

The choice of heuristic creates a fundamental trade-off:

• Perfect Heuristic (h(n) = true cost): A* would expand nodes only on the optimal path, achieving minimal search effort. This is rarely possible.
• Zero Heuristic (h(n) = 0): A* degenerates into Dijkstra's Algorithm, which is optimal but may explore many unnecessary nodes.
• Strong, Admissible Heuristic: A heuristic that provides a tight, accurate estimate (like Euclidean distance) dramatically reduces the search space (nodes expanded) while maintaining optimality. The closer h(n) is to the true cost without exceeding it, the more efficient A* becomes.

In heterogeneous fleet orchestration, A* is adapted for priority-based routing:

• Dynamic Cost Maps: The g(n) cost can incorporate real-time factors like congestion zones, floor traction, or no-go areas for specific agent types.
• Priority as Cost: A high-priority task can be modeled by reducing the perceived g(n) cost along its potential path, causing the algorithm to favor it.
• Multi-Objective Heuristics: h(n) can estimate not just distance, but time-to-deadline or energy consumption, guiding agents toward routes that satisfy multiple constraints. This makes A* not just a pathfinder, but a core planner for efficient, prioritized spatial-temporal scheduling.

Dijkstra's algorithm is a foundational graph search algorithm that finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It operates by iteratively exploring the nearest unvisited node, guaranteeing optimality but without the goal-directed efficiency of A*.

• Key Difference: Lacks a heuristic function, treating all unexplored paths equally.
• Use Case: Ideal for scenarios where the entire cost map is needed or no admissible heuristic is available.
• Foundation: A* can be seen as an extension of Dijkstra's that uses a heuristic to guide the search.

A heuristic function is a problem-specific estimation technique used in informed search algorithms like A* to approximate the cost from a given state to the goal state. It guides the search towards more promising paths, dramatically improving efficiency over blind search.

• Admissibility: For A* to guarantee optimality, the heuristic must never overestimate the true cost to the goal (e.g., Euclidean or Manhattan distance for grid maps).
• Consistency (Monotonicity): A stronger property ensuring the heuristic estimate from a node to the goal is not greater than the step cost to a successor plus the estimate from that successor.
• Design Trade-off: More accurate heuristics lead to fewer expanded nodes but may be computationally expensive to calculate.

A priority queue is an abstract data type that manages a set of elements each with an associated priority. Elements with the highest (or lowest) priority are served first. It is the core data structure for efficiently selecting the next node to explore in A* Search.

• Implementation: Typically implemented with a binary heap or Fibonacci heap, providing O(log n) time for insert and extract-min operations.
• In A*: Used to store the open set, ordered by the sum f(n) = g(n) + h(n), where g(n) is the cost from the start and h(n) is the heuristic estimate to the goal.
• Critical Role: The efficiency of the priority queue's operations directly impacts the overall performance of the A* algorithm.

Dynamic replanning refers to algorithms that efficiently update paths when the environment changes, without recomputing from scratch. Lifelong Planning A (LPA)** and D Lite* are incremental versions of A* designed for this purpose.

• LPA*: Reuses previous search results to find a new optimal path after edge cost changes, maintaining consistency between searches.
• D Lite*: Specifically designed for navigation in partially unknown environments, often used in robotics. It replans from the goal back to the start, efficiently handling new obstacle discoveries.
• Application: Essential for real-world logistics and robotics where maps are updated with new obstacles, traffic, or agent positions.

The Vehicle Routing Problem is a combinatorial optimization problem that seeks the optimal set of routes for a fleet of vehicles to service a set of customers. It generalizes the Traveling Salesperson Problem and is a core challenge in logistics.

• VRP with Time Windows (VRPTW): A critical variant where deliveries must occur within specified time intervals, adding a temporal constraint to spatial routing.
• Relation to A*: A* is often used as a subroutine within VRP solvers to find the shortest path between two customer locations on a road network graph.
• Complexity: Solving VRP optimally is NP-hard, leading to the use of metaheuristics (genetic algorithms, local search) that incorporate pathfinding algorithms like A*.

Multi-objective optimization deals with problems involving multiple, often conflicting, objectives (e.g., minimize travel time, minimize energy use, maximize safety). The Pareto frontier is the set of all optimal trade-off solutions.

• Pareto Optimal: A solution where no objective can be improved without worsening another.
• Beyond A*: Standard A* minimizes a single cost function. Multi-objective A* (MOA*) variants search for the set of Pareto-optimal paths.
• Use in Routing: Essential for heterogeneous fleet orchestration, where different agent types (e.g., fast AMR vs. efficient manual cart) have different cost profiles for the same route.