Notifications
R
Artificial Intelligence (Using GOAP + Utility Theory)
Showcase
296
0
This is one of my university projects that I worked on with 3 other programmers. It features a simulation of Eindhoven Airport. The people at the airport all use a so called "Planner" that determines (using utility theory) the best path to complete a certain task.
While we were planning the technical design for this project, we initially wanted to use behaviour trees. However, we discovered that a Goal Oriented Action Planner (GOAP) will be much more flexible for quickly adding new tasks for the agents. a GOAP is also much easier to manage if the amount of tasks grow.
The structure is designed as follows: There are Agents, All agents have their own Planner which determines the agents current Action. Actions have Preconditions which are also actions. (e.g. a precondition for boarding the plane would be checking in and going through customs).
The code below shows how the planner creates a plan. It first builds a graph (or tree) recursively. It will all the paths that lead to the target goal (action). Once the graph is build, the nodes (which contain the actions) can be traversed back (using cost) to find the most efficient way of reaching the target action.
/// <summary> /// Creates a plan of actions for a specified goal. Returns true if a plan was found. /// </summary> /// <param name="currentState">The current state of the agent.</param> /// <param name="airportState">The current state of the airport.</param> /// <param name="actionOutput">Ouputs the plan of actions for the specified goal. Should be empty</param> /// <param name="goals">The end goals of the plan.</param> /// <returns>Returns true if a plan was found.</returns> public bool MakePlan(GoapAgent agent, Stack<GoapAction> actionOutput, GoapGoal[] goals) { var node = new Node(null, agent.State, null, 0); var leaves = new List<Node>(); var actions = _availableActions.ToList(); foreach (var action in actions) action.Reset(); var foundPlan = BuildGraph(node, leaves, actions, goals); if (!foundPlan) return false; var n = leaves.Aggregate((Node)null, (acc, item) => acc == null || acc.cost > item.cost ? item : acc); while (n != null) { if (n.action != null) actionOutput.Push(n.action); n = n.parent; } return true; } /// <summary> /// Creates all available plans for the specified goals. /// </summary> /// <param name="parent">The parent node.</param> /// <param name="leaves">A list with all possible plans. Should be empty when passed.</param> /// <param name="availableActions">All the available actions.</param> /// <param name="goals">The goals of the plan.</param> /// <returns></returns> private bool BuildGraph(Node parent, List<Node> leaves, List<GoapAction> availableActions, GoapGoal[] goals) { bool success = false; foreach (var action in availableActions) { if (action.Preconditions.All(x => x(parent.state))) { var actionState = new GoapState(); action.ChangeState(actionState); var affectedState = actionState.MergeState(parent.state); var node = new Node(parent, affectedState, action, parent.cost + action.Cost); if (goals.All(x => x(affectedState))) { leaves.Add(node); success = true; } else { var actions = new List<GoapAction>(availableActions.Where(x => x != action)); if (BuildGraph(node, leaves, actions, goals)) success = true; } } } return success; }
For more information about this project visit: http://robertkn.com/project/ai/
R
Robert
6
Comments