WK9: Path Finding Algorithms

• Artificial Intelligence Programming
• Higher Education (degree)

Welcome Week 9

Path Finding Algorithms

Module Lecturer: Dr Raghav Kovvuri

Email: [e-mail]

Scope

Scope of Today’s Session:

• Introduction to Path Finding: Purpose and relevance.
• A* Search Algorithm: Core concepts and implementation.
• Real-world Applications: Examples and case studies.

Real-world Analogies:

• GPS Navigation: Finding the shortest route.
• Robotic Navigation: Navigating a warehouse.
• Video Games: NPC pathfinding and decision-making.

Path Finding Fundamentals

What is Path Finding?

Definition: Path finding is the process of determining an optimal route between points.

Connection to Search Algorithms: Builds upon search techniques, considering weights and heuristics for improved accuracy.

Key Applications:

Navigation Systems: Real-time route optimization.

Robotics and Automation: Efficient movement in constrained environments.

Gaming: Smooth NPC and character movement.

Analogy: Similar to how a GPS system calculates the best route by evaluating distance, time, and obstacles.

Discussions (1)

• Dijkstra Algorithm.
• Greedy Best-First Search.

Submit to Canvas

A* Algorithm Fundamentals*

Key Components:

Open Set: Collection of nodes to be evaluated.

Closed Set: Nodes already evaluated.

Heuristic Function: Guides the search process.

Path Reconstruction: Retraces steps from goal to start to build the optimal path.

The A* algorithm is an informed search algorithm, meaning it leverages a heuristic function to guide its search towards the goal. This heuristic function estimates the cost of reaching the goal from a given node, allowing the algorithm to prioritize promising paths and avoid exploring unnecessary ones.

           The  A* algorithm is a powerful and widely used graph traversal and path finding algorithm. It finds the shortest path between a starting node and a goal node in a weighted graph. 

Implementing A* algorithm 

Python Code Implementation:

This implementation sets up an A* algorithm using a priority queue for efficient node evaluation.

Download A_star.py

Understanding Heuristics

Selecting Heuristics:

• Heuristics are essential for A* efficiency, influencing search direction.

Manhattan Distance: Suitable for grid-based maps without diagonal movement.

def manhattan_distance(p1, p2):

    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

Euclidean Distance: Better for maps where diagonal movement is possible.

def euclidean_distance(p1, p2):

    return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)**0.5

Discussion: Which heuristic would you choose for a grid-based game versus an open-world setting?

Discussions (2)

Algorithm Comparisons:

A* vs. Dijkstra’s: Pros and cons of heuristic-based search.

A* vs. BFS: Efficiency in path length and execution time.

Submit to Canvas

 Real-world Applications

Video Games

• NPC movement
• Strategic planning

Robotics

• Navigation
• Motion planning

GPS Systems

• Route planning
• Traffic avoidance

Key Takeaways

Summary:

• A* Algorithm: Combines cost and heuristics for efficient pathfinding.
• Applications: From virtual simulations to real-world autonomous systems.
• Flexibility: Can adapt to a wide range of environments and needs.