Python A* Search Algorithm for Pathfinding

Last update on December 21 2024 07:18:00 (UTC/GMT +8 hours)

Write a Python program that implements the A* search algorithm for a pathfinding problem.

Pathfinding Problem:

Imagine you have a map or a grid, and you want to find the shortest path from one point (start point) to another point (goal point) on this map/grid.

A Search Algorithm:*

A* search is a popular algorithm used for pathfinding in artificial intelligence and computer science.

It's an informed search algorithm, meaning it uses information about the problem domain to guide its search.

A* balances between the cost of reaching a node from the start and the estimated cost of reaching the goal from that node.

A* maintains two lists: open list and closed list.

It starts from the start point and expands nodes based on their total cost, which is the sum of the cost to reach that node from the start and an estimated cost to reach the goal from that node.

At each step, it selects the node with the lowest total cost from the open list and expands it.

It continues this process until it reaches the goal point or exhausts all possible paths.

Key Components:

Actions: A* needs to know what actions are possible from each node (e.g., moving up, down, left, right).

Transition Model: A* needs to know how these actions move from one node to another.

Cost Function: A* needs to know the cost of each action (e.g., moving one step might have a cost of 1).

Heuristic Function: A* needs a heuristic function to estimate the cost from each node to the goal (e.g., straight-line distance).

Priority Queue: A* uses a priority queue to efficiently select the node with the lowest total cost.

Example:

Suppose you have a grid representing a map with obstacles.

You want to find the shortest path from the top-left corner to the bottom-right corner.

Actions could be moving up, down, left, or right.

The transition model determines how each action moves from one cell to another..

A* will explore the grid, prioritizing cells with lower total costs, until it finds the shortest path to the goal.

Sample Solution:

Python Code :

import heapq

# Define a class to represent a node in the graph
class Node:
    def __init__(self, state, parent=None, action=None, cost=0, heuristic=0):
        self.state = state            # Current state
        self.parent = parent          # Parent node
        self.action = action          # Action taken to reach this node
        self.cost = cost              # Cost from start node to this node
        self.heuristic = heuristic    # Heuristic estimate of cost to goal

    # Compare nodes based on total cost (cost + heuristic)
    def __lt__(self, other):
        return (self.cost + self.heuristic) < (other.cost + other.heuristic)

# Define the A* search function
def astar_search(start_state, goal_state, actions, transition_model, cost_fn, heuristic_fn):
    # Initialize start node
    start_node = Node(state=start_state, cost=0, heuristic=heuristic_fn(start_state))

    # Priority queue for open nodes
    open_nodes = []
    heapq.heappush(open_nodes, start_node)

    # Set of explored states
    explored = set()

    while open_nodes:
        # Pop node with lowest total cost from priority queue
        current_node = heapq.heappop(open_nodes)

        # Check if goal state reached
        if current_node.state == goal_state:
            return get_solution(current_node)

        # Add current state to explored set
        explored.add(current_node.state)

        # Generate successor states
        for action in actions(current_node.state):  # Fix: Call actions function with current state
            next_state = transition_model(current_node.state, action)
            if next_state not in explored:
                cost = current_node.cost + cost_fn(current_node.state, action, next_state)
                heuristic = heuristic_fn(next_state)
                next_node = Node(state=next_state, parent=current_node, action=action, cost=cost, heuristic=heuristic)
                heapq.heappush(open_nodes, next_node)

    return None  # No solution found

# Function to reconstruct the solution path
def get_solution(node):
    path = []
    while node:
        path.append((node.state, node.action))
        node = node.parent
    return list(reversed(path))

# Example usage:
if __name__ == "__main__":
    # Define example functions and parameters for pathfinding problem
    def actions(state):
        return ['up', 'down', 'left', 'right']

    def transition_model(state, action):
        if action == 'up':
            return (state[0] - 1, state[1])
        elif action == 'down':
            return (state[0] + 1, state[1])
        elif action == 'left':
            return (state[0], state[1] - 1)
        elif action == 'right':
            return (state[0], state[1] + 1)

    def cost_fn(state, action, next_state):
        return 1

    def heuristic_fn(state):
        return abs(state[0] - goal_state[0]) + abs(state[1] - goal_state[1])

    # Define start and goal states
    start_state = (0, 0)
    goal_state = (3, 3)

    # Perform A* search
    solution = astar_search(start_state, goal_state, actions, transition_model, cost_fn, heuristic_fn)
    print("Solution:", solution)

Output:

Solution: [((0, 0), None), ((0, 1), 'right'), ((0, 2), 'right'), ((1, 2), 'down'), ((2, 2), 'down'), ((2, 3), 'right'), ((3, 3), 'down')]

Explanation:

• Node Class:
  Represents a node in the graph with attributes for the current state, parent node, action taken to reach this node, cost from the start node, and heuristic estimate of cost to the goal.
• A Search Function (astar_search):*
  
• Implement the A* search algorithm to find the shortest path from the start state to the goal state.
• Utilize a priority queue to explore nodes with lower total cost (cost + heuristic) first.
• Expands nodes, generates successor states, and adds them to the priority queue until the goal state is reached.
• Helper functions:
  get_solution: Reconstructs the solution path from the goal node to the start node.
• actions: Defines possible actions from a given state.
• transition_model: Defines how each action transitions from one state to another.
• cost_fn: Computes the cost of an action from one state to another.
• heuristic_fn: Computes the heuristic estimate of cost from a state to the goal state.
• Example usage:
  Demonstrates how to use the A* search function with example functions and parameters for a pathfinding problem.
• Defines start and goal states, along with functions for actions, transition model, cost, and heuristic.
• Performs A* search to find the shortest path and prints the solution.

Python Code Editor :

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Python Data Validation Library using Dataclasses and type hints.
Next: Python File Synchronization Tool.