blocksworld_project.py

"""
Project:
BlocksWorld Implementation - Heuristic Search Problem -implemented using Heap Data Structure.
Author: @Anil B Murthy
Software used: Enthought Canopy Environment
Hardware: HP Spectre Intel i7 7th Gen 2.7 GHz
"""

import sys
import time
import random
import copy
from heapq import heappop, heappush, heapify
import numpy as np

class Node:
    """
    Creates a node.
    Attributes of a node -
    --> state: representation of configuration of blocks.
    --> depth_g: No of moves performed so far to go from the initial node to the current node = g(n).
    --> parent: Parent Node - Node from which current state was obtained.
    --> children: Nodes that can be generated by using a single move from current state.
    --> heuristic: Estimate to goal state.

    """
    def __init__(self):
        self.state = []
        self.depth_g = 0
        self.parent = None        
        self.children = []
        self.heuristic = None
        
    """        
    Another implementation-
    class Node:
        """"""
        Creates a node.
        Attributes of a node -
        --> g = g(n) = Path length so far from root(initial state) to the current node in the graph -
        No of moves performed so far to go from the initial node to the current node.
        --> f(n) - priority - the whole optimization or result is based on this value of f(n) - g(n) + h(n) = g + h;
        where h is the heuristic
        --> Matrix/ list - adjacency matrix or list - to store the state of the node - Configuration of blocks.
    
        """"""
    
        def __init__(self, blocklist, parent = [], g=0, h=0, f = None):
            self.g = g
            self.h = h #f = g + h
            self.f = g+h
            self.parent = parent
            self.blocklist = blocklist      #list of lists that represents the state.
    
    
        def successor(state):       #State ~ Node object
            no_stacks = len(state.blocklist)
            # Total numnber of legal moves/ possible children for a state are - n*(n-1) where n is the number of stacks.
            matrix = state.blocklist
            for i in range(no_stacks):
                for j in range(no_stacks):
                (len(matrix[i]) - 1)    #last element of every stack
        
    Heuristic 1: Number of Blocks out of place - Initial Heuristic test

    Heuristic 2: 'Closeness' to goal state - stack resemblence.
    
    def compute_heuristics(self):
        self.heuristic = num_of_blocks(self.state) + self.depth_g
        index_count = 0
        for alphabet in self.state[0]:
            if self.state[0].index(alphabet) == ENUMERATE.get(alphabet):
                self.heuristic = self.heuristic - 1
                index_count = index_count + 1	
            else:
                break	
        self.heuristic += len( self.state[0][index_count : ])
         
    Heuristic 3:Overall Complexity to reach goal state estimation Heuristic: Attempted below
        """

    def compute_heuristics(self):
        self.heuristic = self.depth_g + 5*num_of_blocks(self.state)
        #stack0_sorted_length = number of blocks sorted in Stack 0.
        stack0_sorted_length = 0
        #stack0_unsorted_length = number of blocks in stack 0 that are not sorted (if) after a certain set of sorted blocks.
        stack0_unsorted_length = 0 
        #num_blocks_above_next = Total number of blocks above the next required block according to stack 0; The next required block may be present in any stack.        
        num_blocks_above_next = 0
        #num_empty_stacks = Total number of stacks that have no blocks        
        num_empty_stacks = 0
        for alphabet in self.state[0]:
            if self.state[0].index(alphabet) == ENUMERATE.get(alphabet):
                stack0_sorted_length += 1
            else:
                break
        stack0_unsorted_length = len(self.state[0]) - stack0_sorted_length
        
        for stack_number in range(1, len(self.state), 1):
            if INVERSE_MAPPING[stack0_sorted_length] in self.state[stack_number]:                
                num_blocks_above_next = len(self.state[stack_number]) - self.state[stack_number].index(INVERSE_MAPPING[stack0_sorted_length])
                

        if ((num_of_blocks(self.state) - stack0_sorted_length) > (len(self.state) - 1)):
            for stack in self.state:
                if len(stack) == 0:
                    num_empty_stacks += 1
                    
        self.heuristic += (-5)*stack0_sorted_length + 2*stack0_unsorted_length + 2*num_blocks_above_next + num_empty_stacks
    
      
    def get_heuristics(self):
        return self.heuristic

    """ set depth & get depth sub routines"""
    def set_depth(self, depth_g):
        self.depth_g = depth_g

    def get_depth(self):
        return self.depth_g
 
    """ set state & get state sub routines""" 				
    def set_state(self, state):
        self.state = state

    def get_state(self):
        return self.state

    """ set parent & get parent sub routines"""
    def set_parent(self, parent):
        self.parent = parent
        
    def get_parent(self):
        return self.parent

    """ Generate Child Nodes """ 
    def child_node(self):
        children = []
        for i in range(len(self.state)):        #iterating over all stacks
            if len( self.state[i] ) == 0:
                continue
            else:
                for j in range(len(self.state)):
                    if i == j:
                        continue
                    curr_stack = copy.deepcopy(self.state)
                    curr_stack[j].append(curr_stack[i].pop())
                    children.append(curr_stack)
		
        return children

""" A* search algorithm """
def astar(root):
    frontier = []
    visited = set([])
    closed = set([])
    visited.add(tuple(tuple(instance) for instance in root.get_state()))
    heappush(frontier, (root.get_heuristics() , root))
    count = 0 
    print 
    while frontier :
        count += 1
        if count == 10000:
            print " Iteration limit reached. Goal State out of bounds !! "
            sys.exit()
		
        element = heappop(frontier)
        parent = element[1]
        
        print "Iteration no.= ", count, "\tQueue = ", len(frontier), "\tDepth = ", parent.get_depth()
        closed.add(tuple(tuple(element) for element in parent.get_state()))
        if touch_goal(parent.get_state()):
            print "\nGoal State reached: Success !!"
            print "\nThe total number of iterations are:" + str(count)
            print "\nThe frontier size is:" + str(len(frontier))
            return parent
        else:
            for child_state in parent.child_node():
                if tuple(tuple(element) for element in child_state) in closed:
                    continue
                else:
                    #set parameters for child node - Instantiate child as a node & set attributes
                    child = Node()
                    child.set_state(child_state)
                    child.set_parent(parent)
                    child.set_depth(parent.get_depth() + 1)
                    
                    # set heuristic after setting depth
                    child.compute_heuristics()
                    
                    # check if child is in frontier 
                    if tuple(tuple(ele) for ele in child.get_state()) in visited:
                        # iterate through heap , check if heuristic of node in heap is more than child, if so delete the heap element and add child
                        index = 0
                        for priority, node in frontier:
                            if node.get_state() == child.get_state() :
                                if child.get_heuristics() < node.get_heuristics():
                                    frontier[index] = frontier[-1]
                                    frontier.pop()
                                    heappush(frontier, (child.get_heuristics(), child))
                                    heapify(frontier)
                                    break
                                else:
                                    # if heuristic of child is more than the state in heap set child to None for gc 
                                    child = None
                                    break
                            else:
                                index += 1
                    else:
                        heappush(frontier, (child.get_heuristics(), child))
                        visited.add(tuple(tuple(ele) for ele in child.get_state()))	
		


def getpath(goal):
    path = []
    path.append(goal)
    while goal.get_parent() !=  goal:
        goal = goal.get_parent()
        path.insert(0, goal)
    for node in path[1:    ]:
        print "\nNext Move:"
        printstate(node.get_state())

def num_of_blocks(stacks):
    count = 0
    for stack in stacks:
        count += len(stack)
    return count
    
def touch_goal(stacks):
    count = 0
    for alphabet in stacks[0]:
        if stacks[0].index(alphabet) == ENUMERATE.get(alphabet):
            count += 1
        else:
            return False
    if count == num_of_blocks(stacks):
        return True
    else:
        return False

def printstate(state):
    for i in range(len(state)):
        print i+1,  '|' , state[i]

# ENUMERATE - Dictionary to Enumerating alphabets in order; In Java - enum operator used
ENUMERATE = { "A" : 0 , "B" : 1 , "C" : 2 , "D" : 3 , "E" : 4, "F" : 5 , "G" : 6 , "H" : 7 , "I": 8 , "J" : 9 , "K" : 10, "L" : 11, \
   "M": 12, "N" : 13, "O" : 14 , "P" : 15, "Q" : 16 , "R" : 17, "S" : 18 ,"T" : 19 , "U" : 20 , "V" : 21 , "W" : 22 , "X" : 23 , "Y" : 24 , "Z" : 25 }

INVERSE_MAPPING = dict((v, k) for k, v in ENUMERATE.iteritems())


if (len(sys.argv) != 3):
    print("\nError:- Run file using: \n Linux: 'python <file_location/>blocksworld_project.py <number of blocks> <number of stacks>'\n Enthought Canopy/Idle environments: %run <file_location/>blocksworld_project.py <number of blocks> <number of stacks>")
    sys.exit()

numOfBlocks, numOfStacks = int(sys.argv[1]), int(sys.argv[2])
list_of_blocks, ground_state = [], []
for i in range(numOfBlocks):
    list_of_blocks.append(INVERSE_MAPPING[i])

random.shuffle(list_of_blocks)
ground_state = map(list, np.array_split(list_of_blocks, numOfStacks))
print "\nThe Initial State is: "
printstate(ground_state)
# ground_state is the starting(initial) state.
# root = root of search tree for A* Search
root = Node()
root.set_parent(root)
root.set_state(ground_state)
root.set_depth(0) 
root.compute_heuristics()
start = time.time()
goal = astar(root)
stop = time.time()
print "Total execution time = " + str(stop - start) + " s."
print "\nGoal State reached at a depth of " + str(goal.get_depth())
print "\nInitial State: "
printstate(root.get_state())
print "\nSequence of moves according to obtained search path is: "
getpath(goal)