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")

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: