Interactive Pathfinding Algorithms

#ALGORITHMS #AI #VISUALIZATION

Project Overview

A comprehensive comparison of three different approaches to pathfinding: A* Search, Q-Learning, and Auto-regressive Beam Search. Each algorithm demonstrates unique characteristics in how it explores and solves pathfinding problems, visualized through interactive animations.

Algorithm Details

A* Search Algorithm

A* Search: Optimal path finding with heuristic guidance

A best-first search algorithm that combines Dijkstra's completeness with heuristic guidance. Key components:

g(n): Actual cost from start to current node n
h(n): Heuristic estimate of cost from n to goal (Manhattan distance)
f(n) = g(n) + h(n): Total estimated cost for prioritization
Guaranteed to find optimal path when h(n) is admissible
Memory-efficient exploration using heuristic guidance

Q-Learning Algorithm

Q-Learning: Reinforcement learning approach to pathfinding

A model-free reinforcement learning approach that learns optimal actions through experience:

State-Action Value Function (Q-table) tracks expected rewards
Temporal Difference updates learn from experience
ε-greedy exploration balances exploration and exploitation
Adaptable to dynamic environments
Improves performance through repeated trials

Auto-regressive Beam Search

Auto-regressive Search: Beam search with parallel path expansion

Treats pathfinding as a sequence generation problem:

Maintains k-best partial paths (beam width)
Parallel path expansion and evaluation
Scoring combines path length and heuristic estimates
Efficient balance of exploration and computation
Suitable for complex path planning scenarios

Implementation Highlights

A* Search Core


def a_star_search(self):
    frontier = [(0, start)]  # priority queue of (f_score, state)
    came_from = {start: None}
    g_score = defaultdict(lambda: float('inf'))
    g_score[start] = 0
    
    while frontier:
        _, current = heapq.heappop(frontier)
        if current == goal:
            return self._reconstruct_path(came_from, current)
            
        for neighbor in self.get_neighbors(current):
            tentative_g = g_score[current] + 1
            if tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score = tentative_g + self.manhattan_distance(neighbor, goal)
                heapq.heappush(frontier, (f_score, neighbor))

Q-Learning Implementation


def q_learning_search(self, n_episodes=1000):
    Q = defaultdict(lambda: defaultdict(float))
    for episode in range(n_episodes):
        state = self.start
        while state != self.goal:
            if random.random() < epsilon:
                action = random_action()
            else:
                action = argmax(Q[state])
            
            next_state, reward = self.take_action(state, action)
            Q[state][action] += alpha * (
                reward + gamma * max(Q[next_state].values()) - Q[state][action]
            )
            state = next_state

Auto-regressive Search


def autoregressive_search(self, beam_width=5):
    beam = [(self.score(start), [start])]
    while not found_goal:
        candidates = []
        for score, path in beam:
            current = path[-1]
            for neighbor in self.get_neighbors(current):
                new_path = path + [neighbor]
                new_score = self.score_path(new_path)
                candidates.append((new_score, new_path))
        beam = sorted(candidates)[:beam_width]

Maxence Boels