Search Quest : Exploring A* and its variations
AI Club, IITM
How do we find the best path? And what if our safest algorithm isn’t enough?� ��
The Speaker
Adithya Rajagopalan
Mechanical Engineering | 3rd year
Agenda
Can you find the best path?
Algorithmize it!
What exactly does “best” mean?
Shortest?
Fastest?
Safest?
Least Energy?
Before we search, we need to define what we're optimizing.
Basics of Graphs
Search algorithms traverse these spaces to find optimal paths between start and goal states!
The obvious approach
BFS/DFS - The first algorithms to walk graphs.
BFS (Breadth First Search) | DFS (Depth First Search) |
Traverses through a tree layer by layer. | Traverses through a tree by exploring a node’s subtree first before its neighbouring nodes. |
Queue data structure for storage. | Stack data structure for storage. |
Guarantees shortest path on unweighted graphs. | No guarantee for finding the shortest path. |
O(W) space ; O(V + E) time | O(H) space ; O(V + E) time |
The rise of a star! (A*)
BFS and DFS had some major drawbacks in terms of scalability.
BFS won’t consider path cost.�DFS has no sense of direction.�Neither acknowledge the factor of where the goal is.
What if we combine path costs with a sense of direction?
Search Fundamentals
Distance Metrics
Euclidean : √(Δx² + Δy²)
Manhattan : |Δx| + |Δy|
Chebyshev : max(|Δx|, |Δy|)
Octile : max(dx,dy) + (√2−1)·min(dx,dy)
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
Search Types
Informed Search | Uninformed Search |
Has useful information about the goal beforehand. | Searches without additional info on the goal. |
Uses heuristic functions as an aid. | Uses only problem definition and goal test. |
Usually more efficient, faster, and guided. | Less efficient, slow due to vast search, and an unguided approach. |
Ex. Greedy First Search, A*. | Ex. BFS, DFS. |
Logistics - Cost is just distance
Distance - Shortest distance can be found
Time - Take into account congestion and queues
Energy - Battery-aware routing also changes pathing
Risk - Avoid hazardous zones
The algorithm doesn't decide what ‘best’ means. You do.
C = α·distance + β·time + γ·energy + δ·risk
Find a collision free route in warehouses!
A* variants are widely used for autonomous navigation of warehouse robots.
Cost can include: distance + turning + congestion + battery usage. [Very similar to logistics!]
Also very useful for Dark Factories.
Ah yes, our favorite. NPC pathing!
NPCs in video games surprisingly are implemented a vast majority of times through A* variants!
Problem: NPC needs to navigate a game world toward the player/objective.�Map → graph/grid�Movement cost → g(n)�Distance to target → h(n)�Different terrains can have different costs too.
When the world has constraints, use A*.
Drones and robot navigation in 2D or 2.5D spaces used to be implemented through these algorithms.
Problem: Navigate from start → target while respecting obstacles and constraints.�Nodes: possible positions/states�Edges: feasible movements�Weights: movement cost�Heuristic: estimated distance to target�Objective: shortest / fastest / safest feasible route
The A* Algorithm
A* is best-first search where the priority is an estimate of total path cost.��f(n) = g(n) + h(n)
�f(n) -> Total Solution Cost�g(n) -> Incurred Cost�h(n) -> Estimated Remaining Cost
“If our heuristic never overestimates the remaining cost, A* can still guarantee the optimal solution.”
� h(n) <= h*(n)
Why look further when A* is here?
A* finds the optimal path.
So why would we need anything else?
Why look further when A* is here?
No size limit to OPEN and CLOSED lists during traversal. (Too much Memory)
Huge frontier generation in larger graphs despite strong heuristics. (Too much Computation)
Replanning from scratch wastes computation in case of state space changes. (Environmental Changes)
Each algorithm that has grown from A* aims to resolve these issues.
If there was one thing you could change about A*, what would it be?
The A* family
Speed
wA*�Beam Stack Search
Memory
IDA*�RBFS�SMA*�DCFS�SMGS
Direction
Bidirectional A*
Other Structures
AO*�SSS*�
wA* - A* with a slider
What if I want A* to be faster?
f(n) = g(n) + w·h(n), w > 1
W = 0 : Search behaves same as Uniform Cost Search.
W = 1 : Ordinary A* (Guarantees Optimality).
W > 1 : Heuristic function has higher influence on cost. Search is greedier, no optimality.
W >> 1 : Search behaves almost same as Best First Search.
Gives up Admissibility.
0 1 2 … … …
Weight
Beam Stack - To find, one must forget!
Do we really need to preserve our entire frontier?
Beam Stack - Beam makes up the best K candidates at any stage.
By maintaining only a Beam (segment) of our frontier, we save on time as well as memory!
Usually used in real-time searches when speed and partial accuracy are sufficient.
A* frontier:�● ● ● ● ● ● ● ● ● ●
Beam:�● ● ●
Failure mode:
Discarded branch may contain � best solution!
Bidirectional A* - Look both ways!
Bidirectional A* takes A* Algorithm and applies it at both the Goal State and Start State.
Forward A* → Start (Actual Start) to Goal (Actual Goal) state
Backward A* → Start (Actual Goal) to Goal (Actual Start) state
START → → → → ● Instead of one enormous frontier,� ↑ we have 2 smaller ones!� GOAL ← ← ← ← ●
Recursive Best First Search (RBFS)
Requires lesser memory (Only O(b*d)), thus resolving memory issues from A*.
RBFS keeps track of the best alternative cost besides the current path’s �cost, and updates the parent node values whenever costs exceed the limit.
�Guarantees an optimal solution path when the heuristic choice is admissible.
TRADEOFF → Low memory ; High re-expansion risk (CPU time), a process called “Thrashing”!
Divide and Conquer Frontier Search (DCFS)
Instead of storing the entire search history, keep only the frontier and reconstruct the path when needed.
Recursive reconstruction is done upon finding the goal, to form the optimal path.�
TRADEOFF → Greatly reduces memory requirements at the cost of high recomputation time.
To learn, you must first empty your cup!
SMGS - Sparse Memory Graph Search
Goal: Reduce A*'s memory usage
TRADEOFF → Less memory by taking up more reconstruction/recomputations
The king of all memory saving algorithms.
Iterative Deepening A* (IDA*) takes A*'s heuristic + DFS's memory.
Instead of storing the full massive OPEN list, �IDA searches through DFS only within a certain threshold.�If still not found, just increase the f-value threshold!
TRADEOFF → Linear space search depth in exchange for highly repetitive exploration
What happens when the king has no pawns?
What happens when IDA* is given fixed memory?
Simplified Memory A* (SMA*) takes advantage of full memory when available.�Pruning of high-cost leaf nodes when memory availability is an issue.
Paths are reconstructed in the future as and when required.
TRADEOFF → Fastest fixed memory A* variant, requires heavy reconstruction
Game Tree Algorithms - The hunt for MAX
Game Tree algorithms work to search a tree space to find the highest value possible.�This is called the MAX approach. Mainly implemented in 2-player Zero-Sum games.
Just like how A* was grown into a family, so was MINIMAX algorithm :�
| MINIMAX | Alpha-Beta Pruning | SSS* | AO* |
SSS* - To fight a tree you need to make one
SSS* searches and prunes the original tree whilst constructing its own candidate solution tree!
It explores nodes in order of most to least promising, in a minimax-style search.�Prunes off more effectively than α-β!
TRADEOFF → Better search speed in exchange for Higher memory consumption and implementation complexity
AO* - When just one solution isn’t enough
AO* extends the A* algorithm into AND/OR graphs. �OR - Solve just one alternative�AND - Solve all underlying subproblems�Uses heuristic estimates to find the best solution structure.�Can be used for problem decomposition, planning as well as diagnosis!
Recap.
Problem | Approach |
Need optimal path | A* |
Need more speed | wA* |
Can discard candidates | Beam Stack |
Search from both ends | Bidirectional A* |
Memory is tight | RBFS / IDA* / SMA* |
CLOSED is too large | DCFS / SMGS |
Game tree | SSS* |
AND/OR problem | AO* |
Algorithms in action!
A* - https://youtu.be/vtx07tQ5EII
Beam Stack Search - https://youtu.be/WUqe0_7cn1o
Bidirectional A* - https://youtu.be/RFbzgI9dtd0
Alpha-Beta Pruning - https://youtu.be/6QWZviZF3Tk
Algorithm | Space | Time | Optimality |
DFS | O(b^m) | O(b^m) | Not Optimal |
BFS | O(b^d) | O(b^d) | Optimal for equal cost |
A* | Exponential | Dependent | Optimal |
IDA* | O(d) | Dependent | Optimal for admissible h |
RBFS | O(n) | Dependent | Optimal |
wA* | Exponential | Faster than A* | Bounded quality |
Beam Stack | O(k-depth) | Faster than A* | Generally not optimal |
Cheat Sheet
References
Local Search Algorithms - https://medium.com/@adithyarajagopalan/the-search-for-the-peak-an-introduction-to-local-search-algorithms-75a8312c4f00?sharedUserId=adithyarajagopalan
Adversarial Search Algorithms -
Slide Deck -
https://docs.google.com/presentation/d/1O1nKNo-x5ABzJ18Btl1tg1DX977kq2a6VxOBDehPtoQ/edit?usp=sharing
LinkedIn - https://www.linkedin.com/in/adithyarajagopalan/
What’s your tradeoff?
Thank you!
*Insert QR here*