# Rcjp's Weblog

## August 5, 2006

### GPS – General Problem Solver

Filed under: python — rcjp @ 7:39 pm

A translation from Novig’s PAIP Common lisp…

``` """ In [4]: run gps.py Goal: son at school Goal: car works Goal: shop knows problem Goal: in communication with shop Goal: know phone number Action: look up number Action: telephone shop Action: tell shop problem Goal: shop has money Action: give shop money Action: shop installs battery Action: drive son to school State: have phone book and know phone number and in communication with shop and shop knows problem and shop has money and car works and son at school True """ ```

``` import textwrap def splitrules(rules): return rules and rules.split(" and ") class op(object): def __init__(self, action, preconds, achievements=[], costs=[]): self.action = action self.precons = splitrules(preconds) self.achievements = splitrules(achievements) self.costs = splitrules(costs) school_ops = [op("drive son to school", "son at home and car works", "son at school", "son at home"), op("shop installs battery", "car needs battery and shop knows problem and shop has money", "car works", costs="car needs battery"), op("tell shop problem", "in communication with shop", "shop knows problem"), op("telephone shop", "know phone number", "in communication with shop"), op("look up number", "have phone book", "know phone number"), op("give shop money", "have money", "shop has money", "have money")] def achieve(state, goal, ops, indent=0, pending=set()): if goal in state: return True if pending and goal in pending: # stop oscillating goals print "Oscillating subgoal" return False for op in ops: if goal in op.achievements: savedstate = state[:] for precon in op.precons: if not precon in state: print ' '*indent + "Goal:", precon pending.add(goal) if not achieve(state, precon, ops, indent+2, pending): state = savedstate print "Failed goal:", precondition return False pending.remove(goal) print ' '*indent + "Action:", op.action for achievement in op.achievements: state.append(achievement) for cost in op.costs: state.remove(cost) return True return False def gps(state="", goals="", operations=school_ops): print "Goal:", goals state = splitrules(state) success = True for goal in splitrules(goals): success = success and achieve(state, goal, operations, 2) print 'State:', print textwrap.fill(' and '.join(state), 50) return success print gps(state = "son at home and car needs battery" + " and have money and have phone book", goals = "son at school") ```