a star algorithm with q learning in python

main.py
import numpy as np

# Define the grid environment
grid = np.array([
    [0, 0, 0, 0],
    [0, -1, -1, 0],
    [0, 0, 0, 0],
    [0, -1, 0, 0],
    [0, 0, 0, -1],
    [0, 0, 0, 0]
])

# Define the rewards for each state
rewards = np.array([
    [0, 0, 0, 0],
    [0, -1, -1, 0],
    [0, 0, 0, 0],
    [0, -1, 0, 0],
    [0, 0, 0, -1],
    [0, 0, 0, 0]
])

# Define the Q-learning algorithm
def q_learning(start, goal, alpha, gamma, num_episodes):
    Q = np.zeros_like(rewards)  # Initialize Q-values with zeros
    for episode in range(num_episodes):
        state = start
        while state != goal:
            # Select an action based on the Q-values (e.g. epsilon-greedy policy)
            if np.random.rand() < epsilon:
                action = np.random.choice(len(actions))
            else:
                action = np.argmax(Q[state])

            # Update the Q-value based on the action and expected future rewards
            next_state = actions[action]
            next_reward = rewards[next_state[0], next_state[1]]
            Q[state][action] += alpha * (next_reward + gamma * np.max(Q[next_state]) - Q[state][action])
            state = next_state

    return Q

# Define the A* algorithm
def a_star(start, goal, Q):
    open_list = [(start, 0)]
    closed_list = set()
    g_scores = np.inf * np.ones_like(rewards)
    g_scores[start] = 0
    f_scores = np.inf * np.ones_like(rewards)
    f_scores[start] = heuristic(start, goal)

    while open_list:
        current, _ = min(open_list, key=lambda x: f_scores[x[0]])  # Select the node with the lowest f-score
        open_list = [(node, score) for node, score in open_list if node != current]
        closed_list.add(current)

        if current == goal:
            return True

        for neighbor in actions:
            if grid[neighbor] == -1 or neighbor in closed_list:
                continue

            g_score = g_scores[current] + 1  # Cost to reach the neighbor
            f_score = g_score + heuristic(neighbor, goal)  # Estimated total cost from start to goal through the neighbor

            if f_score < f_scores[neighbor]:
                g_scores[neighbor] = g_score
                f_scores[neighbor] = f_score
                open_list.append((neighbor, f_score))

    return False

# Define the heuristic function (Manhattan distance)
def heuristic(state, goal):
    return abs(goal[0] - state[0]) + abs(goal[1] - state[1])

# Set the hyperparameters
start = (0, 0)
goal = (5, 3)
alpha = 0.1  # Learning rate
gamma = 0.9  # Discount factor
epsilon = 0.1  # Exploration rate
num_episodes = 1000

# Define the actions (up, down, left, right)
actions = [(0, 1), (0, -1), (-1, 0), (1, 0)]

# Run the Q-learning algorithm
Q = q_learning(start, goal, alpha, gamma, num_episodes)

# Run the A* algorithm using the learned Q-values
path_found = a_star(start, goal, Q)

if path_found:
    print("Path found!")
else:
    print("Path not found!")
2936 chars
99 lines