Skip to content

Instantly share code, notes, and snippets.

@antoinealb antoinealb/

Created Apr 24, 2017
What would you like to do?
A python implementation of the goap planner
def satisfies_goal(goal, state):
Checks if the given goal is satisfied by the given world state.
for key, value in goal.items():
if state[key] != value:
return False
except KeyError:
return False
return True
def update_state(state, effect):
Returns the given state updated by the desired effect.
state = dict(state)
return state
def plan(goal, state, actions, max_plan_length=10):
Returns a sequence of element from actions that takes the given state to the goal and the cost associated with the given plan.
# Avoid infinite recurson
if max_plan_length <= 0:
current_cost = float('inf')
current_plan = None
# If the state already satisfies the goal, then no action is required
if satisfies_goal(goal, state):
return [], 0.
# Do a DFS search of the planning tree
for a in actions:
# Abort the search if we do not meet the action pre requisites
if not satisfies_goal(a.preRequisite, state):
# Computes the new path recursively
new_plan = plan(goal,
update_state(state, a.effect), actions,
max_plan_length - 1)
# If we found a plan and it is cheaper than the current cost, then pick
# it
if new_plan is not None:
new_plan, new_cost = new_plan
if a.cost + new_cost < current_cost:
current_plan = [a] + new_plan
current_cost = a.cost + new_cost
return current_plan, current_cost
if __name__ == '__main__':
class GrabWood:
preRequisite = {}
effect = {'hasWood': True}
cost = 8.
class CutLog:
preRequisite = {'hasAxe': True}
effect = {'hasWood': True}
cost = 2.
class GrabAxe:
preRequisite = {}
effect = {'hasAxe': True}
cost = 2.
goal = {'hasWood': True}
state = {'hasWood': False, 'hasAxe': False}
possible_actions = [GrabWood, CutLog, GrabAxe]
plan, cost = plan(goal, state, possible_actions)
for action in plan:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.