Robot Run

Illustrating search on a graph for route planning for

depth first
breadth first
A*

This needs a closed list as we are searching on graphs, not trees

The Game Encoding

In a certain terrain a Robot (R) has to navigate to a Goal (G) avoiding Blocks (B)



In [0]:

    
terrain = [
    ["_", "R", "_", "_"],
    ["B", "_", "B", "_"],
    ["_", "_", "B", "_"],
    ["B", "_", "G", "_"]
]

Basic Game Playing Code



In [0]:

    
from copy import deepcopy

robot_symbol = 'R'
robot_win_symbol = '*'
goal_symbol = 'G'
human_symbol = 'H'
blank_symbol = '_'

def is_robot_win(state):
    for row in state:
        for field in row:
            if field == robot_win_symbol:
                return True
    return False   

def as_string(state):
    s = ''
    for row in state:
        row_string = ''
        for field in row:
            row_string += field + ' '
        s += row_string + '\n'
    return s

def locate(state, what):
    for row_index, row in enumerate(state):
        for column_index, field in enumerate(row):
            if field == what:
                return (row_index, column_index)

def check_robot(state, robot):
    max_row = len(state) - 1
    max_column = len(state[0]) - 1
    if robot[0] < 0 or robot[0] > max_row or robot[1] < 0 or robot[1] > max_column:
        return False
    symbol = state[robot[0]][robot[1]]
    if symbol != blank_symbol and symbol != goal_symbol:
        return False
    return True
            
def robot_moves(state):
    robot = locate(state, robot_symbol)
    left = (robot[0], robot[1] - 1)
    right = (robot[0], robot[1] + 1)
    up = (robot[0] - 1, robot[1])
    down = (robot[0] + 1, robot[1])
    valid_moves = [move for move in (left, right, down, up) if check_robot(state, move)]
    return valid_moves
            
def place_robot(state, robot):
    old_robot = locate(state, robot_symbol)
    new_state = deepcopy(state)
    new_state[old_robot[0]][old_robot[1]] = blank_symbol
    if new_state[robot[0]][robot[1]] == goal_symbol:
        new_state[robot[0]][robot[1]] = robot_win_symbol
    else:
        new_state[robot[0]][robot[1]] = robot_symbol
    return new_state

def expand(state):
    valid_moves = robot_moves(state)
    new_states = [(robot, place_robot(state, robot)) for robot in valid_moves]
    return new_states

Generic Search Code



In [0]:

    
def search(root, generate_open_list, debug=False, verbose=True):
    closed_list = set()
    open_list = []
    meta={}
    
    meta[as_string(root)] = (None, None, 0, 0)
    open_list.append(root)
    
    while open_list:
        if debug:
            print('closed_list', closed_list)
            print('open_list', open_list)

        state = open_list.pop(0)
        
        if is_robot_win(state):
            path = construct_path(as_string(state), meta)
            if debug:
                print('*** goal found ***')
                print(as_string(state))
            if verbose:
                print('nodes visited', len(closed_list))
            return path

        expanded = expand(state)
#         if debug:
#             print('expanded', expanded)
        to_visit = [x for x in expanded if as_string(x[1]) not in closed_list]
#         if debug:
#             print('to visit', to_visit)
        open_list = generate_open_list(state, to_visit, open_list, meta, debug=debug)
        closed_list.add(as_string(state))
        
def construct_path(state, meta):
  path = []
  
  while True:
    row = meta[state]
    if row[0]:
      state = row[0]
      action = row[1]
      path.insert(0, action)
    else:
      break
  
  return path

Depth First

not guarenteed to find the best route
probably not very efficient



In [0]:

    
# https://en.wikipedia.org/wiki/Depth-first_search

def depth_first_kernel(parent, children, open_list, meta, max_depth = 10, debug=False):
    new_open_list = list(open_list)
    
    depth = meta[as_string(parent)][2]
    if depth < max_depth:
        if debug:
            print('visiting level', depth)
            print(as_string(parent))
            
        for action, child in children:
            if child not in open_list:
                meta[as_string(child)] = (as_string(parent), action, depth + 1)
                new_open_list.insert(0, child)
    return new_open_list



In [0]:

    
micro_terrain = [
    ["R", "_"],
    ["_", "G"]
];



In [6]:

    
search(micro_terrain, depth_first_kernel)









    



nodes visited 2






    Out[6]:





[(1, 0), (1, 1)]



In [7]:

    
search(micro_terrain, depth_first_kernel, debug=True)









    



closed_list set()
open_list [[['R', '_'], ['_', 'G']]]
visiting level 0
R _ 
_ G 

closed_list {'R _ \n_ G \n'}
open_list [[['_', '_'], ['R', 'G']], [['_', 'R'], ['_', 'G']]]
visiting level 1
_ _ 
R G 

closed_list {'_ _ \nR G \n', 'R _ \n_ G \n'}
open_list [[['_', '_'], ['_', '*']], [['_', 'R'], ['_', 'G']]]
*** goal found ***
_ _ 
_ * 

nodes visited 2






    Out[7]:





[(1, 0), (1, 1)]



In [0]:

    
# will find best path, but many nodes visited
simple_terrain = [
    ["R", "_", "G"],
    ["_", "_", "B"],
    ["_", "_", "_"]
]



In [9]:

    
# this finds the best path, but it is not guaranteed at all
search(simple_terrain, depth_first_kernel)









    



nodes visited 7






    Out[9]:





[(0, 1), (0, 2)]



In [0]:

    
# search(simple_terrain, depth_first_kernel, debug=True)



In [0]:

    
# will not find best path in depth first
simple_terrain2 = [
    ["R", "B", "G"],
    ["_", "_", "_"],
    ["_", "_", "_"]
]



In [12]:

    
search(simple_terrain2, depth_first_kernel)









    



nodes visited 6






    Out[12]:





[(1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2)]



In [0]:

    
# search(simple_terrain2, depth_first_kernel, debug=True)

Breadth First

Guranteed to find the best path
Might still expand too many nodes



In [0]:

    
# https://en.wikipedia.org/wiki/Breadth-first_search

def breadth_first_kernel(parent, children, open_list, meta, max_depth = 10, debug=False):
    new_open_list = list(open_list)

    depth = meta[as_string(parent)][2]
    if depth < max_depth:
        if debug:
            print('expanding level', depth)
            print(as_string(parent))
            
        for action, child in children:
            if child not in open_list:
                meta[as_string(child)] = (as_string(parent), action, depth + 1)
                new_open_list.append(child)
    return new_open_list



In [15]:

    
print(as_string(simple_terrain))









    



R _ G 
_ _ B 
_ _ _



In [16]:

    
search(simple_terrain, breadth_first_kernel)









    



nodes visited 3






    Out[16]:





[(0, 1), (0, 2)]



In [0]:

    
# search(simple_terrain, breadth_first_kernel, debug=True)



In [18]:

    
print(as_string(simple_terrain2))









    



R B G 
_ _ _ 
_ _ _



In [19]:

    
# will find best path
search(simple_terrain2, breadth_first_kernel)









    



nodes visited 7






    Out[19]:





[(1, 0), (1, 1), (1, 2), (0, 2)]



In [0]:

    
# search(simple_terrain2, breadth_first_kernel, debug=True)

A*

Why do we blindly wander around, don't we know in which direction to walk?



In [0]:

    
# https://en.wikipedia.org/wiki/Admissible_heuristic
# we must not overestimate, which is called "admissible"
# strangely enough, this is admissible, but obviously not perfect
def baseline_estimate_rest_cost(child):
    return 1

# https://en.wikipedia.org/wiki/A*_search_algorithm
def a_star_kernel(parent, children, open_list, meta, estimate_rest_cost = baseline_estimate_rest_cost, max_depth = 10, debug=False):
    new_open_list = list(open_list)

    depth = meta[as_string(parent)][2]
    previous_cost = depth
    if depth < max_depth:
        if debug:
            print('expanding level', depth)
            print(as_string(parent))
            
        for action, child in children:
            if child not in open_list:
                estimated_rest_cost = estimate_rest_cost(child)
                estimated_total_cost = estimated_rest_cost + previous_cost
                meta[as_string(child)] = (as_string(parent), action, depth + 1, estimated_total_cost)
                new_open_list.append(child)
    
        # sort using total cost, expand least total cost first
        new_open_list.sort(key=lambda x: meta[as_string(x)][3])
    return new_open_list



In [22]:

    
print(as_string(simple_terrain))









    



R _ G 
_ _ B 
_ _ _



In [23]:

    
search(simple_terrain, a_star_kernel)









    



nodes visited 3






    Out[23]:





[(0, 1), (0, 2)]

A better heuristic

Best of both worlds: always finds best solution, but visited nodes are minimal for this problem



In [0]:

    
from math import sqrt, pow

def distance(pos1, pos2):
    if pos1 and pos2:
        return sqrt(pow(pos1[0] - pos2[0], 2) + pow(pos1[1] - pos2[1], 2))
    else:
        return 0

def distance_based_estimate_rest_cost(child, debug=False):
    robot = locate(child, robot_symbol)
    goal = locate(child, goal_symbol)
    if debug:
        print('robot', robot)
        print('goal', goal)
        print('distance', distance(robot, goal))
    return distance(robot, goal)



In [25]:

    
search(simple_terrain, lambda *args, **kwargs: a_star_kernel(*args, **kwargs, estimate_rest_cost=distance_based_estimate_rest_cost))









    



nodes visited 2






    Out[25]:





[(0, 1), (0, 2)]



In [0]:

    
# search(simple_terrain, lambda *args, **kwargs: a_star_kernel(*args, **kwargs, estimate_rest_cost=distance_based_estimate_rest_cost), debug=True)



In [0]: