AI Airport Simulation

Contributions: Goal-Oriented Action Planner

Role: AI Programming

Engine: Unity3D

Languages: C#

About

This was a university project made in the scope of 8 weeks. The goal of the project is to create a simulation of passenger boarding in an airport.

Contributions

Goal-Oriented Action Planner

Each passenger uses Utility Theory to determine their goal (e.g. using the toilet, buying food, boarding the plane). Afterwards, the planner is used to map out a route of actions to fulfill that goal. Some actions require pre-conditions in order to be executed, while other actions satisfy those conditions as their result. For a plan to be made, the planner selects the last action that needs to be executed and then recursively finds other actions which satisfy the preconditions of the current action. Starting actions usually have no pre-conditions associated with it.

Implementation

The planner starts from the last action that needs to be executed and goes backwards until it finds an action which has no preconditions or all of which have been fulfilled. It does so several times, if it can find more than one ‘path’ to the goal. Then, it uses the ‘cost’ of an action as a heuristic to determine which plan is the most efficient one and then returns that.

public class GoapPlanner
{
  private GoapAction[] _availableActions;

  /// <summary>
  /// Creates a goal-oriented action planner.
  /// </summary>
  /// <param name="actions">A collection of all actions.</param>
  public GoapPlanner(GoapAction[] actions)
  {
    _availableActions = actions;
  }

  /// <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;
  }
}

Awards

We won best code award for the previous 2 study blocks of our year.