Decision Cycle

From ABL
Revision as of 12:50, 31 July 2006 by Dbueno (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Overview

There are two versions of the decision cycle discussed below. One is the decision cycle without Joint Goals.

(For those who are curious and have access to the ABL source code, the decision cycle is implemented in abl.runtime.BehavingEntity.behave()).


Without Joint Goals

  1. (Kill finished steps.) If needed, adjust the ABT for actions that have finished.
  2. (Update world state.) Else if needed adjust the ABT based on changes in the world.
  3. (Pick next step.) Else pick a leaf step to execute, and execute it.

We will discuss each of the steps in turn.

Step 1: Kill Finished Steps

  1. Delete all transient WMEs.
  2. Check if any in-execution act steps have received a callback from the sensory-motor system indicating that the act has finished executing in the world, with either success or failure. For all act steps that have received a callback since the last decision cycle, the step is appropriately succeeded or failed in the ABT.

Step 2: Update World State

  1. If there are atomic steps to execute (leaf steps that are direct or indirect children of atomic behaviors), choose one and execute it.
  2. Otherwise run the sensors associated with sensory WMEs that appear in currently active continuously monitored conditions (success tests, context conditions, and success conditions), thus updating working memory, and run the active continuously monitored conditions, thus succeeding/failing any steps (success tests) or behaviors (context conditions, success conditions) as necessary.

Step 3: Pick Next Step

Let <math>S</math> be the conflict set, excluding wait steps, executing actions, or steps marked suspended. Let <math>a \ge b</math> indicate that <math>a</math> has at least as high priority as <math>b</math><ref><math>\ge</math> is a total order, since every step has a priority.</ref>.

  1. Construct <math>S_{\ge} = \{ s \in S | \langle \forall s' \in S :: s \ge s' \rangle \}</math>, i.e., <math>S_{\ge}</math> contains the set of highest priority steps in <math>S</math>.
  2. Choose a step <math>f \in S_{\ge}</math> randomly, preferring steps in the current line of expansion<ref>This condition applies iff the prefer current line of expansion heuristic is on.</ref>.

Prefer Current Line of Expansion

In order to help control thrashing between two equal priority behaviors, ABL uses the prefer current line of expansion heuristic. To disable this heuristic, compile a behaving entity using the command line argument -X noCurrentLineOfExpansion. You will generally want to leave this heuristic enabled.

In a given decision cycle, a step may be chosen for execution. The very first step s is chosen according to the rules discussed above without this heuristic. However, once the first step has been expanded, a current line of expansion is defined. Next time the decision cycle needs to choose a step it will prefer a child of s, all other things being equal between the steps.

With Joint Goals

  1. (Execute pending negotiations.) If there are pending negotiations, give them a chance to execute.
  2. (Kill finished steps.) If needed, adjust the ABT for actions that have finished.
  3. (Update world state.) Else if needed adjust the ABT based on changes in the world.
  4. (Pick next step.) Else pick a leaf step to execute, and execute it.


This decision cycle is the same as the decision cycle without joint goals, except that there is an additional step to execute pending goal negotiations. Negotiations are scheduled during step 1 of the decision cycle. When a negotiation is scheduled, it blocks the decision cycle thread and does a bit of work to further the negotiation, such as sending intention messages or checking the current negotiation state. If, in checking the negotiation state, it finds that the negotiation has committed, it performs the appropriate ABT modifications and exits, returning control to the decision cycle. If the negotiation is still waiting to commit (waiting for intention messages from team members), the negotiation blocks (a non-busy wait) and returns control to the decision cycle. When a negotiation is initiated, a negotiation thread containing the continuation for that particular intention is created and registered with the decision cycle.

Negotiation Algorithm

repeat 
    iterate over pending negotiations 
    if a negotiation has not been started, start it 
    else if the negotiation has already completed, remove it 
    else give the negotiation a chance to execute 
until no negotiation completes

Footnotes

<references/>