diff --git a/lab7/b-plan-s.py b/lab7/b-plan-s.py new file mode 100755 index 0000000..f492296 --- /dev/null +++ b/lab7/b-plan-s.py @@ -0,0 +1,8 @@ +execfile('lin_plan.py') +execfile('blocks.py') +## Blocks-world sample : Sussman +buildBlocksPlanner(['a', 'b', 'c'], + ['(clear b)', '(clear c)', '(on c a)', '(on-table b)', '(on-table a)', 'handempty'], + ['(on a b)', '(on b c)']) + +findPlan() diff --git a/lab7/b-plan1.py b/lab7/b-plan1.py new file mode 100755 index 0000000..4d7dba2 --- /dev/null +++ b/lab7/b-plan1.py @@ -0,0 +1,8 @@ +execfile('lin_plan.py') +execfile('blocks.py') +## Blocks-world sample 1. +buildBlocksPlanner(['a', 'b', 'c'], + ['(clear a)', '(clear b)', '(on b c)', '(on-table a)', '(on-table c)', 'handempty'], + ['(on a b)']) + +findPlan() diff --git a/lab7/b-plan2.py b/lab7/b-plan2.py new file mode 100755 index 0000000..b8aed58 --- /dev/null +++ b/lab7/b-plan2.py @@ -0,0 +1,8 @@ +execfile('lin_plan.py') +execfile('blocks.py') +## Blocks-world sample 2. +buildBlocksPlanner(['a', 'b', 'c'], + ['(clear a)', '(clear c)', '(on c b)', '(on-table a)', '(on-table b)', 'handempty'], + ['(on a b)', '(on-table c)']) + +findPlan() diff --git a/lab7/b-plan3.py b/lab7/b-plan3.py new file mode 100755 index 0000000..7dd6e13 --- /dev/null +++ b/lab7/b-plan3.py @@ -0,0 +1,8 @@ +execfile('lin_plan.py') +execfile('blocks.py') +## Blocks-world sample 3. +buildBlocksPlanner(['a', 'b', 'c'], + ['(clear a)', '(clear b)', '(on b c)', '(on-table a)', '(on-table c)', 'handempty'], + ['(on a b)', '(on-table b)']) + +findPlan() diff --git a/lab7/b-plan4.py b/lab7/b-plan4.py new file mode 100755 index 0000000..b49e0a8 --- /dev/null +++ b/lab7/b-plan4.py @@ -0,0 +1,8 @@ +execfile('lin_plan.py') +execfile('blocks.py') +## Blocks-world sample 4: +buildBlocksPlanner(['a', 'b', 'c'], + ['(clear a)', '(clear b)', '(on a c)', '(on-table b)', '(on-table c)', 'handempty'], + ['(on a b)', '(on b c)']) + +findPlan() diff --git a/lab7/b-plan5.py b/lab7/b-plan5.py new file mode 100755 index 0000000..02c133e --- /dev/null +++ b/lab7/b-plan5.py @@ -0,0 +1,8 @@ +execfile('lin_plan.py') +execfile('blocks.py') +## Blocks-world sample 5: +buildBlocksPlanner(['a', 'b', 'c'], + ['(clear a)', '(clear c)', '(on a b)', '(on-table b)', '(on-table c)', 'handempty'], + ['(on a b)', '(on b c)']) + +findPlan() diff --git a/lab7/blocks.py b/lab7/blocks.py new file mode 100755 index 0000000..e8f950f --- /dev/null +++ b/lab7/blocks.py @@ -0,0 +1,73 @@ +# -*- coding: iso-8859-15 -*- +###=================================================================== +### UTILITAIRES POUR LE PLANNING DE BLOCS +###=================================================================== + +## D�finit un op�rateur pickup +def pickupOperator(b): + return ['(pickup '+b+')', + ['(clear '+b+')', '(on-table '+b+')', 'handempty'], + ['(holding '+b+')'], + ['(clear '+b+')', '(on-table '+b+')', 'handempty'], + 1] + +## D�finit un op�rateur putdown +def putdownOperator(b): + return ['(putdown '+b+')', + ['(holding '+b+')'], + ['(on-table '+b+')', '(clear '+b+')', 'handempty'], + ['(holding '+b+')'], + 1] + +## D�finit un op�rateur unstack +def unstackOperator(b1,b2): + return ['(unstack '+b1+' '+b2+')', + ['(on '+b1+' '+b2+')', '(clear '+b1+')', 'handempty'], + ['(holding '+b1+')', '(clear ' +b2+')'], + ['(on '+b1+' '+b2+')', '(clear '+b1+')', 'handempty'], + 1] + +## D�finit un op�rateur stack +def stackOperator(b1,b2): + return ['(stack '+b1+' '+b2+')', + ['(holding '+b1+')', '(clear '+b2+')'], + ['(on '+b1+' '+b2+')', '(clear '+b1+')', 'handempty'], + ['(holding '+b1+')', '(clear '+b2+')'], + 1] + +## Cr�e le plannificateur +## @param blocks Les blocs (a,b,c, ...) +## @param initialSituation La situation initiale +## @param finalSituation La situation � atteindre +def buildBlocksPlanner(blocks, initialSituation, finalSituation): + ops = [] + for b1 in blocks: + for b2 in blocks: + if b1 == b2: + ops = [putdownOperator(b1)] + [pickupOperator(b1)] + ops + else: + ops = [stackOperator(b1, b2)] + [unstackOperator(b1, b2)] + ops + buildPlanner(initialSituation, finalSituation, ops, + consistentBlocks, + lambda s : s.meansEnds() + s.opCost()) + +## D�finit la consistence d'un �tat +## @param s L'�tat +def consistentBlocks(s): + if s.operators and len(s.operators) > 1: + a1 = (s.operators[0]).action + a2 = (s.operators[1]).action + if a1[1:] == a2[1:]: + expr1 = a1[0] + expr2 = a2[0] + if expr1 == 'unstack': + return not expr2 == 'stack' + elif expr1 == 'stack': + return not expr2 == 'unstack' + elif expr1 == 'pickup': + return not expr2 == 'putdown' + elif expr1 == 'putdown': + return not expr2 == 'pickup' + return True + + diff --git a/lab7/lin_plan.py b/lab7/lin_plan.py new file mode 100755 index 0000000..5dbac1e --- /dev/null +++ b/lab7/lin_plan.py @@ -0,0 +1,238 @@ +# -*- coding: iso-8859-15 -*- + +## Liste des op�rateurs: +operators = [] + +## Description de la situation initiale: +initialState = [] + +## Liste des �tats encore � explorer: +openList = [] + +## Heuristique d'ordonnancement pour A*: +heuristicFn = [] + +## Fonction v�rifiant la consistence d'un noeud, c�d si ses buts sont +## coh�rents: +consistentFn = [] + +## Liste des solutions trouv�es: +plannerSolutions = [] + +###=================================================================== +### OPERATEURS +###=================================================================== + +class Operator: + + ## Constructeur + ## @param action Action effectu�e + ## @param preconds Liste des pr�conditions + ## @param addList Liste ajout�e + ## @param deleteList liste enlev�e + ## @cost cost Co�t de l'op�rateur. + def __init__(self, action, preconds, addList, deleteList, cost): + self.action=action + self.preconds=preconds + self.addList=addList + self.deleteList=deleteList + self.cost=cost + + ## Retourne une repr�sentation en string des caract�ristiques de l'op�rateur + def __str__(self): + out = ("\n" % (self.action, self.preconds, self.addList, self.deleteList, self.cost)) + return out + +## D�finit un nouvel op�rateur d'apr�s sa et l'ajoute +## a la variable globale operators. +## @param description Liste [action preconditions add-list delete-list co�t] +def defOperator(description): + global operators + op = Operator(description[0],description[1],description[2],description[3],description[4]) + operators.append(op) + + +###=================================================================== +### ETATS (STATES) +###=================================================================== + +class State: + + ## Constructeur + ## @param goals Les buts de l'�tat. + ## @param operators La liste des op�rateurs appliqu�s � cet �tat pour parvenir a l'�tat final + ## @param cost Le co�t de cet �tat + def __init__(self, goals, ops, cost=0): + self.goals = goals + self.operators = ops + self.cost = cost + + ## Compare deux �tats + ## @param other L'autre �tat � comparer + def __cmp__(self, other): + return self.cost - other.cost + + ## Retourne une repr�sentation en string avec les caract�ristiques de l'�tat + def __str__(self): + out = ("\n" % (self.goals, self.operators, self.cost)) + return out + + ## Retourne True ssi l'�tat est une solution, c�d si ses buts + ## font partie de l'�tat initial. + def isSolution(self): + global initialState + return set(self.goals).issubset(set(initialState)) + + ## Calcule le co�t de l'�tat d'apr�s la fonction heuristique + ## heuristicFn et retourne l'�tat. + def computeCost(self): + global heuristicFn + self.cost = apply(heuristicFn, [self]) + return self + + ## Retourne tous les nouveaux �tats que l'on peut obtenir en + ## appliquant les op�rateurs � l'�tat . + ## @param ops Les op�rateurs � appliquer + def applyOperators(self, ops): + rs = [] + for o in ops: + s = self.applyOperator(o) + if isinstance(s, State): + rs.append(s) + return rs + + ## Applique l'op�rateur a l'�tat s'il est applicable et + ## retourne le nouvel �tat. + ## @param op L'op�rateur � appliquer + def applyOperator(self, op): + global consistentFn + x = self.applicable(op) + if x: + newGoals = list(set(self.goals).union(set(op.preconds)).difference(set(x))) + newOperators = self.operators[:] + newOperators.append(op) + newState = State(newGoals, newOperators) + newState.computeCost() + if apply(consistentFn, [newState]): + return newState + return [] + + ## Verifie que l'op�rateur op peut s'appliquer a l'�tat, c�d que: + ## - aucun pr�dicat de la deleteList de op ne fait partie des + ## buts de l'�tat. + ## - au moins un but de l'�tat est satisfait par un pr�dicat de + ## l'addList de op. + ## Retourne la liste des buts satisfaits par op. + ## @param op L'op�rateur � appliquer + def applicable(self,op): + if len(set(self.goals).intersection(set(op.deleteList))) < 1: + return set(self.goals).intersection(set(op.addList)) + else: + return [] + + ## Analyse moyens-buts; retourne le nombre de buts de l'�tat + ## qui ne sont pas satisfaits par l'�tat initial initialState. + def meansEnds(self): + global initialState + return len(set(initialState).difference(set(self.goals))) + + ## Retourne la somme des co�ts des op�rateurs appliqu�s a l'�tat + ## final pour obtenir l'�tat. + def opCost(self): + if self.operators: + return reduce(lambda x,y: x + y.cost, self.operators, self.cost) + else: + return self.cost + + ## Affiche la solution + def printPlannerSolution(self): + print("== PLANNER SOLUTION ==") + i = 0 + for op in self.operators: + print("Action %s: %s" % (i, op.action)) + i = i+1 + + + +###=================================================================== +### INITIALISATION et CONSTRUCTION +###=================================================================== + +## Initialise et construit un nouveau planificateur. +## @param initState L'�tat initial +## @param goals Les buts +## @param ops La description des op�rateurs +## @param consistent La fonction de consistance +## @param heuristic La fonction heuristique utilis�e par A* +def buildPlanner(initState, goals, ops, consistent, heuristic): + global operators + global initialState + global plannerSolutions + global openList + global consistentFn + global heuristicFn + operators = [] + initialState = initState + plannerSolutions = [] + openList = [State(goals,[],0)] + consistentFn = consistent + heuristicFn = heuristic + for op in ops: + defOperator(op) + return openList[0] + + +###=================================================================== +### RECHERCHE +###=================================================================== + +## Recherche une solution en explorant au plus �tats. +## @param maxSteps Le nombre maximal de pas +def findPlan(maxSteps=1000): + global plannerSolutions + sol, steps = AStarSearch(maxSteps) + if isinstance(sol,State): + print("FOUND A SOLUTION IN %s STEPS\n" % (steps)) + plannerSolutions = [sol] + plannerSolutions + sol.printPlannerSolution() + return sol + elif steps < 0: + print("NO MORE SOLUTIONS (open list exhausted)\n") + else: + print("NO SOLUTION FOUND IN %s STEPS\n" % (steps)) + +## Algorithme de recherche A*. Effectue au maximum pas +## de recherche. N'utilise pas de closed-list. +## Retourne 2 valeurs: +## - la solution trouv�e ou [] si aucune solution n'a �t� +## trouv�e. +## - le nombre de pas de recherche effectu�s. Si openList a +## �t� "vid�e" (c�d il n'y a plus de solutions), cette +## deuxieme valeur sera -1. +## @param maxSteps Le nombre maximal de pas +def AStarSearch(maxsteps): + global openList + step = 0 + while len(openList) > 0: + s = openList[0] + openList = openList[1:] + if s.isSolution(): + return s, step + openList = openList + s.applyOperators(operators) + openList.sort() + step = step + 1 + if step == maxsteps: + return [], step + return [], -1 + + +###=================================================================== +### UTILITAIRES +###=================================================================== + +## Affiche toutes les solutions trouv�es par le planificateur +def printPlannerSolutions(): + global plannerSolutions + print(">>> FOUND %s PLANS <<<" % (len(plannerSolutions))) + for sol in plannerSolutions.revers(): + sol.printPlannerSolution()