Archive for the ‘AI’ tag
Eliza like chatterbot in Python
Basically, the brain takes in a list of two lists that defines it’s
personality : [patternResponsepairs,defefaultReplies].
The pattern response pairs contains a list of patterns and
their corresponding responses.
A PATTERN is a Python list containing any number of the following elements in any order:
WORD: This is a string containing alphabetic characters only. It must match an
element in a SENTENCE exactly as written.
0: This matches any number of WORDs in a SENTENCE.
1: This matches exactly one WORD in a SENTENCE
[0, identifier]: This matches zero or more WORDs in a SENTENCE, and binds them to the identifier.
[1, identifier]: This matches exactly one WORD in a SENTENCE, and binds it to the identifier.
A default response is responses that the bot will spit out when it can’t find a match.
#!/usr/bin/python #This program is free software: you can redistribute it and/or modify #it under the terms of the GNU General Public License as published by #the Free Software Foundation, either version 3 of the License, or #(at your option) any later version. #This program is distributed in the hope that it will be useful, #but WITHOUT ANY WARRANTY; without even the implied warranty of #MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the #GNU General Public License for more details. #For a copy of the license see . # A simple eliza bot in python # import re import random class Agent: def __init__(self,brain): self.patternResponses = [] self.defaultResponses = [] self.Usersname ='' self.Usernametag ='Username' self.defRespIndex =0 self.pronounMap = { #generic pronouns 'i':'you','you':'i', 'my':'your', 'me':'you', 'your':'my', "i've":"you've","we've":"they've", # "you've":"i've","they've":"we've", #some names, these wll get applied if the name #isnt the current user's name 'fred':'he', 'jack':'he', 'jane':'she', } self.change_mind(brain) def change_mind(self,brain): """ Change mind on the fly. To change the Agent's brain """ assert (len(brain) == 2) self.patternResponses = brain[0] self.defaultResponses = brain[1] print "Brain initialized." def tell(self,input): sentence = input.lower().strip().replace('(','').replace(')','').split(' ') bl = [] matchedPat = [] for pat in self.patternResponses: bl = self.pattern_match(pat[0],sentence,[]) if bl == ['FAIL']: continue matchedPat = pat break if bl == ['FAIL']: #choose from a default response # or just append a question mark on the # user's sentence. print '... No pattern Response pair selected.' print '... Choosing a default response.' #Used to be randon using random.choice #but then i noticed that the requirements say that #the same default response may not be used again #before every other one has been used. self.defRespIndex = self.defRespIndex +1 if self.defRespIndex >= len(self.defaultResponses): #reset the counter to 0 self.defRespIndex = 0 ; #Possible improvement: shuffle the default response array, so that # the responses dont come in the same sequence again. #last on got chosen, make the user input into #a question return ' '.join(sentence) + ' ?' else: return ' '.join(self.defaultResponses[self.defRespIndex]) else: print '... Pattern Response pair selected:', pat print '... BL before call to change_pronouns: ',bl blAfter = self.change_pronoun(bl) print '... BL after call to change_pronouns: ',blAfter rep = self.build_reply(pat[1],blAfter) return ' '.join(rep) def make_regexp(self,pattern): """ Convert a pattern list into an equivalent regular expression """ assert(isinstance(pattern,list)) r = ['^'] #for exact matches we prepend ^ and $ to the regexp. usedBackrefs = [] for tok in pattern: if isinstance(tok,str): #WORD r.append('(' + tok +')') elif isinstance(tok, int): # 0 or 1 if tok == 0 : r.append('[a-zA-Z ]*?') # match 0+ word(chars + space), elif tok == 1: r.append('[a-zA-Z]+') # match 1 word else: raise Exception, "Ints can only be 1 or 0, not:", tok elif isinstance(tok, list): #bindinglist pattern list if tok[0] == 0 : #if we havent used this backref yet, then add ?P<name> #and add it to the used backrefs list. if not tok[1] in usedBackrefs: usedBackrefs.append(tok[1]) r.append('(?P<'+tok[1] +'>[a-zA-Z ]*?)') else: #if we have come across his back ref, then add?P=name r.append('(?P='+tok[1]+')') elif tok[0] == 1: if not tok[1] in usedBackrefs: r.append('(?P<'+tok[1] +'>[A-Za-z]+)') usedBackrefs.append(tok[1]) else: #if we have come across his back ref, then add?P=name r.append('(?P='+tok[1]+')') else: raise Exception, "Valid first elems of BL pattern = 1 or 0, not:", tok #for exact matches we prepend ^ and $ to the regexp. #also, we disregard surrounding whitespace. ret = '(\s)*'.join(r) + '$(\s)*' return re.compile(ret) def pattern_match(self,pattern,sentence,bl): """ return the populated binding list if the pattern matches, otherwise return the binding list with the element 'FAIL' """ pat = self.make_regexp(pattern) s = ' '.join(sentence) matches = re.search(pat,s) if (matches == None): # if we dont have a match #then return w/o modifying the bindinglist. return ['FAIL'] bindingList = list(bl) grps = matches.groups() for k in pat.groupindex: b=[] b.append(k) for x in grps[pat.groupindex[k]- 1].split(' '): if x.strip() !='': b.append(x) bindingList.append(b) return bindingList def change_pronoun(self,bl): """ reverses pronouns in a binding list. """ #if the pronoun dic contains a elemen, then #replace it with its corresponding value. bindingList = list(bl) for i in range(len(bindingList)): if isinstance( bindingList[i], list): for j in range(len(bindingList[i])): if j > 0: if self.pronounMap.has_key(bindingList[i][j].lower()): bindingList[i][j] = self.pronounMap[bindingList[i][j]] return bindingList def build_reply(self,respPattern,bindingList): """ build_reply ([[1, 'subject'], 'loves', [0, 'object']], [['subject', 'jane'], ['object', 'ice', 'cream']]) will return ['jane', 'loves', 'ice', 'cream']. """ #convert the bindlingList to a dictionary so thats its easy to #get the binding label bl = {} reply = [] for elem in bindingList: #do the username chack firsdt, the id Username is #only used in relation to the username .This is #so that we can kinda remember the user's name if (elem[0] == self.Usernametag): # if we already have user name set, then # Hi, username , what happend to oldusername if self.Usersname !='': tmp =self.Usersname self.Usersname = elem[1] return [elem[1],'eh?','what','ever','happened','to',tmp] else: self.Usersname = elem[1] if bl.has_key(elem[0]) == elem[1:]: raise Exception, 'Binding list has name collision for: ', elem[0] else: if isinstance(elem,list) and len(elem) > 1: bl[elem[0]] = elem[1:] #else: # print elem, 'binding element ',elem,' has no binded things' for elem in respPattern: if isinstance(elem,list) and len(elem) > 1: x = elem[1] if bl.has_key(x): for y in bl[x]: reply.append(y) #else: # print 'not found in bl:', x else: #anything else, just append to the list. reply.append(elem) return reply def talk(brain): assert((isinstance(brain,list)) and (len(brain) ==2 )) b = Agent(brain) while 1: try: inp = raw_input("> ").lower() except EOFError: print 'Toodle do,\n you can type (quit) if you want be more pleasant.' break if len(inp.strip()) > 0 : if inp.strip().lower() == 'quit': print 'To exit the program, type (quit) [In parentheses]' if inp.strip().lower() == '(quit)': print 'Bye' break else: print b.tell(inp) def start(): defReplys = [ ['Is','that','right?'], ['Excellent'], ['Interesting'], ['You','dont','say'], ['I','wouldnt','have','guessed'] ] patternResps = [ #[[pattern],[response]] #Basics [[0,'my','name','is',[1,'Username'],0],['pleased','to','meet','you',[1,'Username']]], [['hello'],['Good','day']], [['how','are','you',[0,'a']],['Good','How','are','you',[0,'a']]], [['i','am','fine'],['Glad','to','hear','you','are','fine']], [[[1,'a'],'is','fine'],['Glad','to','hear',[1,'a'],'is','fine']], [['no'],['Understood']], [['yes'],['I','see']], [['you','said',[0,'we']],['I may have said ',[0,'we'],'What about it?']], [[[1, 'subject'], 'loves', [0, 'object']],['Laudable','why','does',[1,'subject'],'love',[0,'object'],'?']], [['because'],['Lack of reason is not a reason']], [['i','need',[1,'object']],['why','do','you','need',[0,'object'],'?']], [[[0,'subject'],'needs',[0,'object']],['why','does',[0,'subject'],'need',[0,'object'],'?']], [['how', 'is','your',[0,'object']],['my',[0,'object'],'is','holding','up','well','.do','you','have','a',[0,'object'],'?']], [[[0,'we'],'i','have','a',[0,'thing']],['how','goes', 'it','with','your',[0,'thing'],'?']], [[[0,'we'],'i','have',[0,'thing']],['how','is', 'your',[0,'thing'],'?']], [[[0,'we'],'is','great'],['how','is',[0,'we'],'great','?']], [['i','like',[0,'a']],['Interesting','i','appreciate',[0,'a'],'too']], [['i','said',[0,'we']],['Why','did','you','say',[0,'we']]], [[0,'you',[1,'b'],'me'],['What','gave','you','the','impression','I',[1,'b'],'you ?']], [['i','feel',[0,'a']],['How','long','have','you','felt',[0,'a'],'?']], [['tell',[0,'who'],'about',[0,'sub']],['What','would','I','tell',[0,'who'],'about',[0,'sub'],'that','isn\'t','known','?']], [[0,'brother',0],['My','brother\'s','name','is','Henry.','Do','you','have','any','siblings?']], [[0,'sister',0],['I','dont','have','a','sister.','How','is','your','family','doing?']], #anything that ends with exclamation [[0,'\!'],['Keep calm']], # if its a question that hasnt gotten matched uptil now # do this. Note: This needs to be last to ensure its the last test [[[0, 'question'], '\?'],['What','do','you','mean', [0,'question'],'?']], ] ## Run the tests required in the Project specification talk([patternResps,defReplys]) if __name__=="__main__": start()
Route planner/ airline scheduler in Prolog
My first prolog program. This is something that prolog seems ideal for. It’s a simple route planner that can be used in making flight reservations. Note that this takes into account a padding of atleast 45 mins between flights.
The constraints that the user can specify are :
- City departing from
- City traveling to
- Departure time
- Arrival time
- Day of week for flight
- A route
All of these constraints are optional; the traveller is free to specify only those that are appropriate.
Without further ado, here’s the code(as always, warts and all):
%%This program is free software: you can redistribute it and/or modify %%it under the terms of the GNU General Public License as published by %%the Free Software Foundation, either version 3 of the License, or %%(at your option) any later version. %%This program is distributed in the hope that it will be useful, %%but WITHOUT ANY WARRANTY; without even the implied warranty of %%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the %%GNU General Public License for more details. %%For a copy of the license see <http://www.gnu.org/licenses/>. %% %%  Prolog route planner. %% operator symbol for time structure :- op( 50, xfy, : ). %% Paths between cities path(lp1211, columbus,  charlotte, 11:10, 12:20, [mon, tue, wed, fri, sun ]). path(lp1212, charlotte, columbus , 13:20, 16:20, [mon, tue, wed, fri, sun ]). path(lp1322, columbus, pittsburgh, 11:30,12:40,[tue, thu ]). path(lp1323, pittsburgh, columbus , 13:30, 14:40, [tue, thu ]). path(lp1458, roanoke, charlotte , 09:10, 10:00, [mon, tue, wed, thu, fri, sat, sun]). path(lp1459, charlotte, roanoke , 11:00, 13:50, [mon, tue, wed, thu, fri, sat, sun]). path(lp1472, columbus, charlotte, 20:30, 21:30, [mon, wed, thu, sat]). path(lp1473, charlotte, columbus , 16:30, 19:30, [mon, wed, thu, sat]). path(lp1510, charlotte, roanoke , 08:30, 11:20, [mon, tue, wed, thu, fri, sat, sun]). path(lp1511, roanoke, charlotte , 12:20, 13:10, [mon, tue, wed, thu, fri, sat, sun]). path(lp1613, pittsburgh, charlotte , 09:00, 09:40, [mon, tue, wed, thu, fri, sat]). path(lp1614, charlotte, pittsburgh, 09:10, 11:45, [mon, tue, wed, thu, fri, sat, sun]). path(lp1620, pittsburgh, roanoke , 07:55, 08:45, [mon, tue, wed, thu, fri, sat, sun]). path(lp1621, roanoke , pittsburgh, 09:25, 10:15, [mon, tue, wed, thu, fri, sat, sun]). path(lp1623, roanoke , pittsburgh, 12:45, 13:35, [mon, tue, wed, thu, fri, sat, sun]). path(lp1805, charlotte, pittsburgh, 14:45, 17:20, [mon, tue, wed, thu, fri, sun]). path(lp1806, pittsburgh, charlotte , 16:10, 16:55, [mon, tue, wed, thu, fri, sun]). path(lp4732, charlotte , raleigh , 09:40, 10:50, [mon, tue, wed, thu, fri, sat, sun]). path(lp4733, raleigh , charlotte, 09:40, 10:50, [mon, tue, wed, thu, fri, sat, sun]). path(lp4752, charlotte, raleigh , 11:40, 12:50, [mon, tue, wed, thu, fri, sat, sun]). path(lp4773, raleigh , charlotte, 13:40, 14:50, [mon, tue, wed, thu, fri, sat, sun]). path(lp4822, charlotte, raleigh , 18:40, 19:50, [mon, tue, wed, thu, fri]). path(lp4833, raleigh , charlotte, 19:40, 20:50, [mon, tue, wed, thu, fri]). %% Tests to see H2:M2 is atleast 45 minutes later than H1:M1 canTransfer( H1:M1, H2:M2):- ((60 * (H2 - H1) + ( M2 - M1)) >= 45). %% Valid times are initialized variables %% that are number values validTime(H1:M1):- nonvar(H1), nonvar(M1), number(H1), number(M1). %% is H1:M1 earlier than H2:M2 ? isEarlierThan(H1:M1, H2:M2):- (validTime(H2:M2) -> ((H2 == H1 , M1 < M2) ; (H1 < H2 )) ; (H2 = H1 , M2 = M1) ). %% is H1:M1 later than H2:M2 ? isLaterThan(H1:M1, H2:M2):- (validTime(H2:M2) -> ((H2 == H1 , M1 > M2) ; (H1 > H2 )) ; (H2 = H1, M2 = M1) ). %% Base case: next node is the destination route(From,To,DeptTime,ArrTime,Day,[FlNum],Visited):- findPath(FlNum,From,To,Dept1,Arr1,Day), not(member(To,Visited)), isLaterThan(Dept1,DeptTime), isEarlierThan(Arr1,ArrTime). %% Recursive case: the destinaion may be somewhere out there. route(From,To,DeptTime,ArrTime,Day,[FlNum|Route], Visited):- findPath(FlNum,From,StopOver,Dept1,Arr1,Day), not(member(StopOver,Visited)), route(StopOver,To,Dept2,Arr2, Day,Route,[StopOver|Visited]), isLaterThan(Dept1,DeptTime), isEarlierThan(Arr2,ArrTime), canTransfer(Arr1,Dept2). %% A valid path exists in the same day findPath(FlNum,From,To,FromTime,ToTime,Day):- path(FlNum,From,To,FromTime,ToTime,Days), member(Day,Days). %% plan_route( From_City, To_City, From_Time, To_Time, Day, Route) %% route is list of flight nums, [] is visited flight nums %% Note, actual from_time can be later than From_Time, %%      actual to_time can be earlier than To_Time plan_route(From_City,To_City,From_Time,To_Time,Day, Route):- route(From_City,To_City,From_Time,To_Time,Day,Route,[From_City]).
Simple theorem prover in python
Another python “AI” code. A really simple theorem prover (by refutation).
Expected input format = look at the test cases.
As always warts, excessive comments and all :
#!/usr/bin/python #This program is free software: you can redistribute it and/or modify #it under the terms of the GNU General Public License as published by #the Free Software Foundation, either version 3 of the License, or #(at your option) any later version. #This program is distributed in the hope that it will be useful, #but WITHOUT ANY WARRANTY; without even the implied warranty of #MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the #GNU General Public License for more details. #For a copy of the license see . from string import * class ProofAgent: def __init__(self): """ Declare the knowledge base and negated theorem hash tables. """ self.kb = {} # knowledge base to hold the axioms self.neg = {} # holds the negated theorems self.tested = {} # hash to backup processed axioms def tell(self,lst,hashNum,hashToAdd): """ Add the proposition(s) of this axiom to the hash hashToAdd lst is the lst with the axiom hashNum is the number it should be stored under in the hash table hashToAdd is the hash to add the information to """ if (len(lst) > 0 ): #if the list isn't empty process it. if lst[0] == "AND" : #there should be no ANDs within the axiom #because that isn't allowed. If it was allowed, we would just #process the axiom to reduce it to cnf before a tell. raise Exception, "Clauses are expected to be normalized CNF" if lst[0] == "OR": #skip OR self.tell(lst[1:],hashNum,hashToAdd) else: p = [] #temp to store the propostion p.append(lst[0]) i = 1 while lst[i-1] == "NOT" : # handle chained NOTs p.append(lst[i]) i = i + 1 if hashToAdd.has_key(hashNum): #add the proposition to the hashtable hashToAdd[hashNum].append(join(p,' ')) else: hashToAdd[hashNum] = [] hashToAdd[hashNum].append(join(p,' ')) self.tell(lst[i:],hashNum,hashToAdd) #move on to the next proposition else: return def tellAxiomSet(self,str): """ Split the axioms and call tell to add them to the kb hash table str is the string containing the axioms """ for x in (str.replace('(','').replace(')','').split(',')): ls = x.strip().split(' ') self.tell(ls[1:],ls[0],self.kb) def tellNegatedTheoremSet(self, negated): """ Split the negated theorem and call tell to add it to the negated theorems hash table negated is the string containing the negated theorem """ for x in (negated.replace('(','').replace(')','').split(',')): ls = x.strip().split(' ') self.tell(ls[1:],ls[0],self.neg) def testTheorem(self, theorem): """ Return true if we find the negated theorem in our knowledge base. If we do find it, it is either b itself or in an or with something else. If first case, then we succeed. Otherwise, test the 'wth something' part and carry on. if the last with some thing is true, then we succeed. theorem is the proposition to test. """ for k, v in self.kb.iteritems(): print " Testing ",theorem, " against clause ",k, " ", join(v, " OR " ) if isinstance(v,list): for x in v: if upper(x.strip()) == upper(theorem.strip()): #Originally, I was poping it off the list and continuing, #thereby implicitly creating a clause by trimming the old one. #however, changed it to not remove the knowlede base because #of external requirements. ugly i know. y = list(v) self.tested[k] = y #new for new clause z = list(v) z.remove(x) #remove old clause from dict so that we dont look at it again. del self.kb[k] if (len(z) > 0): #if there are literals to check against, do that id = len(self.kb)+ len(self.tested)+1 # for use with printing out self.kb[id] = z # negate the proposition before sending # it to be tested so that we can find the negation if (z[0].count("NOT") > 0) : return self.testTheorem( z[0].replace("NOT","").strip()) else: return self.testTheorem("NOT " + z[0].strip()) else: #if there are no more literals , we passed. return True return False def resolve(self): """ Return true if the proof succeeds with the kb and negated theorem. Return false otherwise. Expects that the kb and the negated theorems have been set up. """ if ((len(self.kb) == 0 ) or (len(self.neg) == 0)): raise Exception, "Knowledge base or negated thoerem count is zero. \ \nPlease set this up before continuing " testsPassed = True #temp to keep track of tests passed for k, v in self.neg.iteritems(): for item in v : #assumes NOT only appears 1 or 0 times in the theorem if (item.count("NOT") > 0) : testsPassed = testsPassed and (self.testTheorem(item.replace("NOT","").strip())) else: testsPassed = testsPassed and (self.testTheorem("NOT " + item.strip())) return testsPassed def resolve (axioms, negTheorem): """ Interface to convieniently use the agent. """ proofAgent = ProofAgent() proofAgent.tellAxiomSet (upper(axioms)) proofAgent.tellNegatedTheoremSet(upper(negTheorem)) print "-----------------------------------------------------" if (proofAgent.resolve()): print " The proof succeeded\n" else: print " The proof did not succeed\n" def runTests(): """ Run the tests that were provided with the project requirements """ print "Running test 1" a = "((1 NOT P OR Q ), (2 P)) " n = "(0 NOT Q)" resolve(a,n) print "Running test 2" a = "((1 Q OR NOT P), (2 R OR NOT Q), (3 S OR NOT R),(4 NOT U), (5 P)) " n = "(0 NOT Q)" resolve(a,n) print "Running test 3" a = "((1 Q OR NOT P), (2 R OR NOT Q), (3 S OR NOT R),(4 NOT U), (5 P)) " n = "(0 NOT S)" resolve(a,n) print "Running test 4" a = "((1 P OR Q OR NOT R OR S OR NOT U), (2 NOT P),(3 NOT Q), (4 NOT S), (5 U), (6 NOT V))" n = "(0 R OR V)" resolve(a,n) print "Running test 5" a = "((1 P OR Q OR NOT R), (2 R), (3 U))" n = "(0 NOT P)" resolve(a,n) if __name__ == "__main__": runTests()
STRIPS algorithm for blocks world in python
Simple implementation of the STRIPS algorithm with safety net feature for the
blocks world. When I was implementing this, I couldn’t find any reference impls so here is mine, warts and all.
#!/usr/bin/python #This program is free software: you can redistribute it and/or modify #it under the terms of the GNU General Public License as published by #the Free Software Foundation, either version 3 of the License, or #(at your option) any later version. #This program is distributed in the hope that it will be useful, #but WITHOUT ANY WARRANTY; without even the implied warranty of #MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the #GNU General Public License for more details. #For a copy of the license see . #!/usr/bin/python from string import * class Stripper: # A STRIPS-style planner for the blocks world ## Initialization code def __init__(self): """ Initialize the gloal variables, and function dictionaries """ self.worldStack =[] self.goalStack = [] self.plan =[] #token to function mappings self.formulas = { "holding" : self.holding, "armempty": self.armempty, "on" : self.on , "clear": self.clear , "ontable" : self.ontable } self.Operators = {"STACK":self.stack,"UNSTACK":self.unstack, "PICKUP":self.pickup,"PUTDOWN":self.putdown} #safety net tests are denoted by the following as the frst list item. self.SafetyTag = "SAFETYTAG" def populate(self,str,stateStack): """ Helper function that parses str according to expectations and adds to the sateStack passed in. """ for x in (str.lower().replace('(','').replace(')','').split(',')): ls = x.strip().split(' ') stateStack.append(ls) stateStack.reverse() def populateGoal(self,str): """ Populate the goal stack with data in str. """ self.populate(str,self.goalStack) # add original safety check goalCheck = [] goalCheck.append(self.SafetyTag) for g in self.goalStack: goalCheck.append(g) self.goalStack.insert(0,goalCheck) def populateWorld(self,str): """ Populate the world state stack with data in str. """ self.populate(str,self.worldStack) ## ---------------------------------------------------- ## Predicate logic atomic formula functions ## All these functions: ## Add the required operator, ## the safety net, ## and the preconditions for the operator ## ---------------------------------------------------- def holding(self): topG = self.top(self.goalStack) assert (topG[0] == "holding"),"expected holding" assert (len(topG) == 2 ),"expected 2 for holding" #if on table, add pickup operator #if stacked, add unstack operator if (self.isOnTable(topG[1])): ## add operator pickup self.goalStack.append(["PICKUP", topG[1] ]) #add safety net self.goalStack.append([self.SafetyTag, ["armempty"], ["ontable", topG[1]],["clear", topG[1]]]) #add the preconditions self.goalStack.append(["armempty"]) self.goalStack.append(["ontable", topG[1]]) self.goalStack.append(["clear", topG[1]]) else: #add UNSTACK, y = self.getItemUnder(topG[1]) # get y from world, i.e w/e's under topG[1] if y == 0 : raise Exception, "Nothing is under " + topG[1] self.goalStack.append(["UNSTACK",topG[1],y]) #add safety check self.goalStack.append([self.SafetyTag, ["armempty"], ["clear", topG[1]],["on", topG[1],y]]) #add the preconditions self.goalStack.append(["armempty"]) self.goalStack.append(["clear", topG[1]]) self.goalStack.append(["on",topG[1],y]) def armempty(self): topG = self.top(self.goalStack) assert (topG[0] == "armempty"),"expected armempty" assert (len(topG) == 1 ),"expected 1 for armempty" ## add operator put down x = self.getHoldingItem() #get x from world state #i.e get whatever variable is being held if ( x == 0 ): raise Exception, " No item being held, this is a problem. Exiting." self.goalStack.append(["PUTDOWN", x]) #add safety check self.goalStack.append([self.SafetyTag, ["holding",x]]) #add preconditions self.goalStack.append(["holding",x]) def on(self): topG = self.top(self.goalStack) assert (topG[0] == "on"),"expected on" assert (len(topG) == 3 ),"expected 3 for on" ## add operator assumes not in world state #add STACK, self.goalStack.append(["STACK",topG[1],topG[2] ]) #add safety check self.goalStack.append([self.SafetyTag, ["holding", topG[1]],["clear", topG[2]]]) #add the preconditions self.goalStack.append(["holding", topG[1]]) self.goalStack.append(["clear", topG[2]]) def clear(self): topG = self.top(self.goalStack) assert (topG[0] == "clear"),"expected clear" assert (len(topG) == 2 ),"expected 2 for clear" ## add the preconditions to the goalstack. #add UNSTACK, x = self.getItemOn(topG[1]) # get x from world, i.e w/e's on top of topG[1] if x == 0 : raise Exception, "Nothing is on " + topG[1] self.goalStack.append(["UNSTACK", x, topG[1]]) #add safety check self.goalStack.append([self.SafetyTag, ["armempty"], ["clear", x],["on", x, topG[1]]]) #add the preconditions self.goalStack.append(["armempty"]) self.goalStack.append(["clear", x]) self.goalStack.append(["on", x,topG[1]]) def ontable(self): topG = self.top(self.goalStack) assert (topG[0] == "ontable"),"expected ontable" assert (len(topG) == 2 ),"expected 2 for ontable" ## add the preconditions to the goalstack. ## add putdown self.goalStack.append(["PUTDOWN", topG[1]]) #add safety check self.goalStack.append([self.SafetyTag,["holding", topG[1]]]) #add preconditions self.goalStack.append(["holding",topG[1]]) ## ---------------------------------------------------- ## Functions that modify the world ## All these functions: ## Delete and add states to the world state stack ## as required by their corresponding operator ## ---------------------------------------------------- def stack(self,subgoal): #deletions self.worldStateRemove(["clear",subgoal[2]]) self.worldStateRemove(["holding",subgoal[1]]) #addition self.worldStateAdd(["armempty"]) self.worldStateAdd(["on",subgoal[1],subgoal[2]]) def unstack(self,subgoal): #deletions self.worldStateRemove(["on",subgoal[1],subgoal[2]]) self.worldStateRemove(["armempty"]) #addition self.worldStateAdd(["holding",subgoal[1]]) self.worldStateAdd(["clear",subgoal[2]]) def pickup(self,subgoal): #deletions self.worldStateRemove(["ontable",subgoal[1]]) self.worldStateRemove(["armempty"]) #addition self.worldStateAdd(["holding",subgoal[1]]) def putdown(self,subgoal): #deletions self.worldStateRemove(["holding",subgoal[1]]) #addition self.worldStateAdd(["ontable",subgoal[1]]) self.worldStateAdd(["armempty"]) ## ---------------------------------------------------- ## Solver ## Attempts to solve the problem using the setup ## goal and world states ## ---------------------------------------------------- def solve(self): """ Attempts to solve the problem using STRIPS Algorithm Note: You need to setup the problem prior to running this by using populateWorld and populateGoal using a well formatted string. """ if (not len(self.worldStack) > 0) or (not len(self.goalStack) > 0): print "\nNothing to do.\nMake sure you populate the problem using\n \ populateWorld and populateGoal before calling this function." return while len(self.goalStack) > 0 : #if the subgoal is in world state if self.top(self.goalStack) in self.worldStack: # pop it from the stack subgoal = self.goalStack.pop() #if that item is an operator, elif (self.Operators.has_key( self.top(self.goalStack)[0].upper())): subgoal = self.goalStack.pop() #store it in a "plan" self.plan.append(subgoal) # and modify the world state as specified self.Operators[(subgoal[0])](subgoal) #if the item is a safety check elif (self.SafetyTag == self.top(self.goalStack)[0].upper()): safetyCheck = self.goalStack.pop() for check in safetyCheck[1:]: if not (check in self.worldStack): print " Safety net ripped.\n Couldn't contruct a plan. Exiting...",check return else: #find an operator that will cause the #top subgoal to result if (self.formulas.has_key(self.top(self.goalStack)[0])): self.formulas[self.top(self.goalStack)[0]]() else: raise Exception, self.top(self.goalStack)[0] + " not valid formula/subgoal" #or add to goal stack and try, but not doing that for now. print "\nFinal Plan:\n" , for step in self.plan : print " " ,join(step," ").upper() ## ---------------------------------------------------- ## Utility functions ## ---------------------------------------------------- def getItemUnder(self,item): """ Returns the item that is on the passed in item in the world state. Returns 0 if no such item exists """ for x in self.worldStack: if x[0] == "on" and x[1] == item : return x[2] return 0 def isOnTable(self, item): """ Returns true if the item is on the table. False otherwise. """ return (["ontable",item] in self.worldStack) def getHoldingItem(self): """ Returns the item that is being held in the world state. Returns 0 if no such item exists """ for x in self.worldStack: if x[0] == "holding": return x[1] return 0 def getItemOn(self, item): """ Returns the item that is on the passed in item in the world state. Returns 0 if no such item exists """ for x in self.worldStack: if x[0] == "on" and x[2] == item : return x[1] return 0 def worldStateAdd(self,toAdd): """ Adds a state to world state if the state isn't already true """ if toAdd not in self.worldStack: self.worldStack.append(toAdd) def worldStateRemove(self, toRem): """ Tries to remove the toRem state from the world state stack. """ while toRem in self.worldStack: self.worldStack.remove(toRem) def top(self,lst): """ Returns the item at the end of the given list We dont catch an error ecause thats the error we want it to throw. """ return lst[len(lst) -1 ] def runTests(): """ Test function to run all tests provided with project requirement documentation and a few more. """ ## Test 1 print "\n\n Running Test 1 \n" ws = "((on C B), (ontable B), (ontable A), (clear A), (clear C), (armempty))" gs = "((on A B), (ontable B), (clear A))" s = Stripper() s.populateGoal(gs) s.populateWorld(ws) s.solve() ## Test 2 print "\n\n Running Test 2 \n" ws = "((on A B), (on C D), (ontable B), (ontable D), (clear A), (clear C), (armempty))" gs = "((on C B), (on D A), (ontable B), (clear D))" s = Stripper() s.populateGoal(gs) s.populateWorld(ws) s.solve() ## Test 3 print "\n\n Running Test 3 \n" ws = "((clear A), (armempty), (clear D), (ontable C), (ontable D), (on B C), (on A B))" gs = "((ontable C), (ontable D), (on B D), (clear A), (on A C), (clear B))" s = Stripper() s.populateGoal(gs) s.populateWorld(ws) s.solve() # Test 2 with extra goal state print "\n\n Running Test 2 with extra Goal State \n" ws = "((on A B), (on C D), (ontable B), (ontable D), (clear A), (clear C), (armempty))" gs = "((on C B), (on D A), (ontable B), (clear D),(ontable A))" s = Stripper() s.populateGoal(gs) s.populateWorld(ws) s.solve() if __name__ == "__main__" : runTests()