Planner

version 2/080503 by Nate Cull

  • Home page
  • Beginning
  • Previous
  • Next



  • Section - Main Routines

    [This is the main entry point for calling Planner. It will find an action that satisfies the desired relation/object/object triad, and then attempt to execute that action.]

    To have (A - a person) plan an action for (C - a planning-relation) with (P1 - an object) and (P2 - an object):
        if debugging planner, say "Planner: starting planning for [A].";
        if debugging planner, say "Planner: testing goal 1: [C] [P1] [P2]: [run paragraph on]";
        change the planning actor to A;
        change the requested relation to C;
        change the requested param1 to P1;
        change the requested param2 to P2;
        change the planned action to no-action;
        change the planned param1 to no-object;
        change the planned param2 to no-object;
        if goal C with P1 and P2 is true begin;
            change the planned action to success-action;
            if debugging planner, say "true, no work to do[line break]";
        otherwise;
            if debugging planner, say "false, generating plans [run paragraph on]";
            clear the goal table;
            choose row 1 in the Table of Goals;
            change the Token entry to the requested relation;
            change the Param1 entry to the requested param1;
            change the Param2 entry to the requested param2;
            change the Parent entry to 0;
            change the Plan entry to 0;
            change the Step entry to 0;
            expand goal 1;
            advance all goals;
        end if;
        if debugging planner begin;
            if the planned action is no-action, say "Planner: no action chosen";
            otherwise say "Planner: choosing [the planned action] [the planned param1] [the planned param2]";
            say "[paragraph break]";
        end if;
        execute the planned action;



    [The core loop. Fill up the goal table line by line, reading goals as we come to them, considering each one, and if we can't satisfy it then spawning new subgoals and adding them to the end of the table. If we can fully satisfy a goal, then we end and return the action of that one as our chosen action.

    My terminology is a little confusing as I sometimes use the words 'plan' and 'goal' apparently interchangeably. That's because of the way the data is stored. Let's have some definitions:

    A Goal is a triad of Relation, Object, Object. (The Cat Is-on The Mat). It represents a piece of world state that we are actively trying to make true. Goals are related to one another in a tree structure. There is a top-level Goal which may have multiple child goals, and so on.

    A Plan is a set of (Goal, Goal, Goal... Action). If every goal, evaluated in sequence from left to right, is true, then the actor should take the suggested Action.

    So every Goal can have multiple Plans, and every Plan can have multiple Goals.

    You'd think the best way to store this would be with a tree structure: Goals spawning Plans spawning Goals and so on. And you'd probably be right. But since we don't have dynamic memory allocation and can't easily do trees, we use a table instead. And each row of that table indicates *both* a Goal *and* a Plan, depending on context. Somewhat confusing. That is to say:

    * The top row indicates the top-level Goal.
    * All new rows added to the table indicate separate Plans which are suggested as ways of satisfying outstanding Goals.
    * We examine each Plan, checking each of its Goals, and eventually we either return an Action, or stop at a Goal which is blocking us. When that happens, we mark up the table row to now indicate a *Goal*, and continue on.

    So as we go on, each line in the table that we've visited consists of a Goal. Lines that we've added but not yet visited indicate unevaluated Plans.

    Each row has:
    * Parent -the Goalrow which this is a plan or goal for
    * Plan - the Plan number of the Parent goal which this is a plan for
    * Step - (once we've turned from a Plan to a Goal) the Step number of this Plan at which we stopped evaluating because we found a not-currently-true Goal or an Action
    * Token - either an Action or a Relation, or else a Marker (a kind of note-to-self used for internal communication between the Planner routines)
    * Param1 - the first Object of the Action or Relation - only set once we have a Goal or Action
    * Param2 - the second Object of the Action or Relation - only set once we have a Goal or Action

    Adding new Plans for a Goal I have called Expanding.
    Scanning a Plan, checking each of its subgoals, I have called Advancing.

    ]

    To advance all goals:
        repeat with G running from 2 to the number of filled rows in the Table of Goals begin;
            advance goal G;
            if an action was planned, change G to 9999;
        end repeat;



    [Advancing a Goal: Here we're scanning through each item in the current plan, checking what we've got, and if it's a subgoal, testing if it's true or not. If it's false, then we check if it's unique (ie, not listed as one of our prior goals). This prevents endless recursive loops - we deal with each goal once and only once, regardless of how many parent goals need it. If it's an action, we return that as our choice - this means we pick the first action that we find, ie, the action with the smallest number of goal-expansion steps. This should generally mean we take the shortest path toward getting our way.

    To read each Step, we call the 'planning' rulebook, passing the desired relation/object/object and the desired Plan and Step through the 'desired...' global variable block. We increment Step each time. We stop once we don't get a response from the rulebook. This means that plans need to use consecutive Step numbers starting from 1. The rulebook will be hit once for every Step, plus once for counting Steps, of every Plan, plus one more for counting Plans. So if a plan requires expensive calculations, it is a good idea to test that 'desired plan' is set to the plan number before you run the calculation, or you'll be running it lots of times and throwing the result away.

    ]

    To advance goal (G - a number):
        choose row G in the Table of Goals;
        let our parent be the Parent entry;
        let our plan be the Plan entry;
        change the suggested token to the Token entry;
        change the suggested param1 to the Param1 entry;
        change the suggested param2 to the Param2 entry;
        choose row our parent in the Table of Goals;
        let our relation be the Token entry;
        let our param1 be the Param1 entry;
        let our param2 be the Param2 entry;
        let the final step be 0;
        if debugging planner, say "Planner: reading goal [G] (plan [our plan] for goal [our parent])[line break]";
        repeat with Sx running from 1 to 9 begin;
            suggest a goal for our relation with our param1 and our param2 for plan our plan at step Sx;
            if the suggested token is a planning-marker begin;
                change Sx to 9999;
                choose row G in the Table of Goals;
                change the Token entry to no-plan;
                change the Param1 entry to no-object;
                change the Param2 entry to no-object;
            end if;
            if the suggested token is a planning-relation begin;
                if debugging planner, say "Planner: testing step [Sx]: [suggested token] [suggested param1] [suggested param2]: [run paragraph on]";
                if goal suggested token with suggested param1 and suggested param2 is false begin;
                    if debugging planner, say "false ";
                    if goal the suggested token with the suggested param1 and the suggested param2 is unique begin;
                        if debugging planner, say "and unique, generating plans [run paragraph on]";
                        choose row G in the Table of Goals;
                        change the Token entry to the suggested token;
                        change the Param1 entry to the suggested param1;
                        change the Param2 entry to the suggested param2;
                        change the Step entry to Sx;
                        change the final step to Sx;
                        change Sx to 9999;
                        expand goal G;
                    otherwise;
                        if debugging planner, say "but duplicate, cancelling plan[line break]";
                        choose row G in the Table of Goals;
                        change the Token entry to no-plan;
                        change the Param1 entry to no-object;
                        change the Param2 entry to no-object;
                        change the Step entry to Sx;
                        change the final step to Sx;
                        change Sx to 9999;
                    end if;
                otherwise;
                    if debugging planner, say "true";
                end if;
            end if;
            if the suggested token is a planning-action begin;
                if debugging planner, say "Planner: testing step [Sx]: [the suggested token] [the suggested param1] [the suggested param2]: action[line break]";
                change the planned action to the suggested token;
                change the planned param1 to the suggested param1;
                change the planned param2 to the suggested param2;
                choose row G in the Table of Goals;
                change the Token entry to the suggested token;
                change the Param1 entry to the suggested param1;
                change the Param2 entry to the suggested param2;
                change the Step entry to Sx;
                change the final step to Sx;
                change Sx to 9999;
            end if;
        end repeat;


    [Expanding a Goal: Here we are just dropping new empty lines onto the goal table to indicate Plans we have yet to explore. About all the information we need is the Parent and Plan entries. The rest we will look up in the Parent row once we get there.]


    To expand goal (G - a number):
        choose row G in the Table of Goals;
        let our relation be the Token entry;
        let our param1 be the Param1 entry;
        let our param2 be the Param2 entry;
        repeat with P running from 1 to 9 begin;
            suggest a goal for our relation with our param1 and our param2 for plan P at step 1;
            if the suggested token is no-plan begin;
                [we've run out of plans]
                change P to 9999;
            otherwise;
                [add new goal, checking for out of space]
                if the number of blank rows in the Table of Goals is greater than 0 begin;
                    [add a new goal, as just a parent/plan/step entry]
                    let the last row be the number of filled rows in the Table of Goals;
                    increase the last row by 1;
                    choose row the last row in the Table of Goals;
                    change the Parent entry to G;
                    change the Plan entry to P;
                    change the Step entry to 1;
                    change the Token entry to plan-pending;
                    change the Param1 entry to no-object;
                    change the Param2 entry to no-object;
                    if debugging planner, say "[P] [run paragraph on]";
                otherwise;
                    if debugging planner, say "Planner: goal table is full, ignoring new goal.";
                end if;
            end if;
        end repeat;
        if debugging planner, say "[line break]";