TABLE OF CONTENTS

1 INTRODUCTION 1

2 WORLD MODEL 1

3 KNOWLEDGE AREAS 2

4 CYCLIC FUNCTIONALITY 15

5 SYSTEM GOALS 15

6 INTENTION STRUCTURE 16

7 THE main() FUNCTION 16

8 PRIMITIVE FUNCTION INTERFACING 17

9 BUILDING AND RUNNING A UM-PRS BASED APPLICATION 21

10 UM-PRS INTERPRETER 22

11 EMPIRICAL STUDIES 24

12 CHANGES/MODIFICATIONS FROM UM-PRS V2.9 25

References 25

UM-PRS is composed of four components: a database representing the current world model, a library of plans called Knowledge Areas (KAs), a primitive function library and primitive function interface for performing low-level functions, and an intention structure that maintains the runtime state of the set of currently active goals. The user deals explicitly with the first three of these components. This document describes the purpose of each of these components, how they interact, any files that are necessary, and any related representation and syntax. The system’s functionality, which in part depends upon the intention structure, is also described. Throughout the document we describe any of the constraints and limitations of the current implementation. A demonstration system, including of all of the necessary components for a simple, but complete, running system, is included with the UM-PRS package.

The UM-PRS execution cycle is very similar to that originally discussed for PRS in [1,2,3,4,6]. Changes to the world model or posting of new goals triggers the system to search for all valid (based upon the goal and context) KAs that might be used to deal with the situation. The system interpreter may then select one KA from this collection, called the SOAK (Set Of Applicable KAs), and intend it, which places the instantiated KA (it has a variable binding particular to the situation) onto the UM-PRS intention structure, the system’s multi-goal runtime stack. Alternatively, the system may continue to execute the intention currently on the intention structure. This is discussed in more depth in Section 10.

The world model holds the facts that represent the current state of the world. Information that might be kept there includes state variables, sensory information, conclusions from deduction or inferencing, modeling information, etc. Each world model entry is of the form:

relation-name argument1 argument2 ... argumentN;

Each relation with the string identifier relation-name has a user-specified implicit ordering and semantic label for each argument in the relation. For example, a relation with the name tree might specify the height, species, and color of a tree, such as in:

tree 20 "Maple" "Red";

Specification of the world model consists of creating a text file containing the keyword FACTS: followed by the list of initial world model relations. UM-PRS parses the world model specification before execution and is furnished to the planning system as described in Section 9. An example world model specification, drawn from a robotics application, might be as shown below:

FACTS:

robot_status "Ok";

partner_status "Ok";

robot_initialized "False";

robot_localized "False";

robot_registered "False";

robot_position 10000 10000 0;

robot_location "Unknown";

self "CARMEL";

partner "BORIS";

object_found "False";

object_delivered "False";

comm_status "Ok";

plan_empty "False";

destination "Room4";

next_room "Room3";

next_node "Node12";

Throughout KAs, variables are represented by a text identifier preceded by a $ symbol. Variables may be used throughout a KA, and are primarily used in actions in the KA body, in the KA context, and in a KA’s purpose expression. Note that variables should never be used in the initial world model (the reason for this will become evident later). Each of the parts of a KA is described below in more detail. Before this, though, we discuss expressions, an important UM-PRS representation scheme.

$variable_name_1

12345

12.45

"abc def"

//

// arithmetics with a floating point number and an integer

//

(+ 0.123 -123) // plus

(- 1 2.0 3 4.0) // minus

(/ 30 2.0 3 -4) // division

(* 2.3 3.4 4.5 5.6 6.7) // multiplication

(% 12 3) // modulo

(abs -3) // absolute value

//

// string concatenation

//

(+ "abc" "efg" "\\" "\n" "\r" "\t" "\f")

(+ "\b" "\a" "\v" "Hex \xff" "Octal \77")

//

// Boolean

//

(== $a 10 $b) // equal

(!= "abc" $b "abc") // not equal

(< 10 5) // less than

(<= 10.5 5) // less than or equal

(> $a 10 $b $c) // greater than

(>= $a "hello" $b "world") // greater than or equal

//

// Logical

//

(and (> $a 10) (< $a 100)) // and

(&& (> $a 10) (< $a 100)) // and

(or (> $a 10) (== $a 0)) // or

(|| (> $a 10) (== $a 0)) // or

(not (== $a 10)) // not

(! (== $a 10)) // not

Note that most functions allow mixed (integer and floating point) number operations. Boolean conditionals, however, cannot have mixed argument types, in general. It is illegal, for example, to compare a string with an integer.

Furthermore, most functions can have single or multiple arguments, and quite often more than two arguments. An example of this can be seen in the string concatenation examples above.

The body of a KA describes the sequence of actions, a procedure, to be taken in order to accomplish a goal. The body may contain provided UM-PRS actions and user-defined primitive functions, and can be organized into branches which are conditional executed and loops which can be conditionally repeated. An example of a KA is shown below. It is not complete followed by a description of each of its components.

KA {

NAME:

"Example KA"

DOCUMENTATION:

"This is a nonsensical KA that shows all of the possible actions"

PURPOSE:

ACHIEVE ka_example;

CONTEXT:

FACT task_complete "False";

BODY:

QUERY determine_task $task;

FACT problem_solved $task $solved;

OR

{

TEST (== $solved "YES");

WAIT user_notified;

RETRACT working_on_problem "True";

}

{

TEST (== $solved "NO");

ACHIEVE problem_decomposed;

ATOMIC

{

ASSERT working_on_problem "True";

MAINTAIN problem_decomposed;

};

ASSIGN $result (* 3 5);

};

UPDATE (task_complete) (task_complete "True");

FAILURE:

UPDATE (ka_example_failed) (ka_example_failed "True");

EXECUTE print "Example failed. Bailing out"

}

ACHIEVE goal_name parameter1 parameter2 ... parameterN :PRIORITY expression;
An achieve action causes the system to subgoal from the currently executing goal. This then triggers the system to search for KAs in the KA library that can satisfy the goal goal_name given the current context. Parameters can be used as arguments to the goal to be achieved and can also be used to get return values back from the invoked KA. If the invoked KA fails, and the achieve was within a KA body, the achieve action fails as would any other KA body action. The failure semantics for system goals (i.e., top level goals) is different, however, and is explained in Section 5.

An achieve action can optionally specify the priority of the goal using the keyword :PRIORITY expression after the parameters. If the priority is not specified, it has the default priority 0. The details of how the goal priority is interpreted will be explained in Section 10.

AND { active-sequence1 } ... { action-sequenceN };
where action-sequence (also called a branch) is one or more of any of the actions listed here and N > 0. The semantics of an and action is that the interpreter will execute each of the branches in turn, with the first branch listed executed first. If all of the branches succeed, then the action succeeds. If any branch fails, then the entire action fails.

AND

{

EXECUTE print $x;

}

{

EXECUTE print $y;

};

ASSERT relation_name argument1 argument2 ... argumentN;
Information is placed into the world model using an assert action. Assertion causes the system to search the world model for the given relation name. If it finds a world model entry with the same relation name and the same argument values, the action does nothing. Otherwise, the action appends the asserted fact, with all of the arguments evaluated into values, onto the world model. All variables and expressions must be evaluable to either a string, floating point number, an integer number, or an address (an integer).

NOTE: To modify a relation in the world model, use the update action, to be explained below.

ASSIGN variable expression;
Variables can also be assigned values based on such things as mathematical computations using the assign action. The given expression is evaluated and the variable is assigned the resulting string, floating point number, integer number, or address (pointer). This action always succeeds.

ATOMIC {action1; action2; ... actionN; }

The sequence of actions action1, action2, ... actionN are all executed before control is given back to the interpreter. Normally, the interpreter performs several functions between each action (see Section 10.) This might, in some cases, cause the system to interrupt execution of a sequence of actions in the middle of the sequence. Using the atomic action bypasses this interpreter activity, guaranteeing that the sequence of actions will complete. This action succeeds when the entire sequence executes successfully, and fails if the sequence fails.

// A typical situation to use an ATOMIC construct - where early

// actions in the sequence might have otherwise caused the

// interpreter to prematurely interrupt execution of the sequence.

ATOMIC

{

UPDATE (debug_mode) (debug_mode "False");

UPDATE (run_mode) (run_mode "True");

EXECUTE print "Now entering run mode.\n";

};

DO { action1; action2; ... actionN; } WHILE : action0;

The sequence of actions action1, action2, ... actionN are executed and then, if the action0 (typically a test action) succeeds, the sequence of actions are repeated. This continues until action0 fails, and the action after the do is then executed, or until one of action1, action2,... actionN fails, whereby the entire do action fails.

DO

{

EXECUTE print $x;

ASSIGN $x (+ $x 1);

} WHILE : TEST (> $x 10);

EXECUTE function_name parameter1 parameter2 ... parameterN;
Primitive functions may be executed by using an execute action. Primitive functions implement the low-level functionality of a complete system. Certain primitive functions, such as print are already implemented. The primitives that come with UM-PRS are listed in Section 8.3. Parameters can be passed as arguments and can also be used to return values. See Section 8 for documentation on how to write new primitive functions.

FACT relation_name argument1 argument2 ... argumentN;
Information from the world model can be accessed using the fact action. The world model is searched for the first entry with the given relation name that has matching constant and bound variable arguments. Any arguments that are unbound variables are assigned the appropriate values from the matched world model entry. If no match is found, the action fails.

FAIL ;
This action always fails. It can be used to explicitly cause a branch or a KA to fail without having to resort to some more obscure method.

LOAD file_list;

MAINTAIN goal_name parameter1 parameter2 ... parameterN;
A maintain goal instructs the system that the given goal must be reattained if it ever becomes unsatisfied. Parameters can return values. If there are no applicable KAs for goal goal_name, then the action fails. maintain goals are not currently implemented.

OR { active-sequence1} ... { action-sequenceN };
where action-sequence (also called a branch) is one or more of any of the actions listed here, and N > 0. The semantics of an OR action is that the interpreter will execute each of the branches in turn, with the first branch listed executed first. If any of the branches succeed, then the action succeeds. If all branches fail, then the entire action fails.

{

TEST (< $z 0);

EXECUTE print "Error: value < 0!\n";

}

{

TEST (>= $z 0);

ASSIGN $altitude $z;

};

QUERY goal_name parameter1 parameter2 ... parameterN;
A query action is functionally identical to an achieve action. It is provided to allow the programmer to be more explicit about the semantics of the action’s goal (information acquisition, in particular). If the invoked KA fails, the query action fails.

RETRACT relation_name argument1 argument2 ... argumentN;
One or more entries in the world model can be removed from the database using a retract action. The system searches the world model for all entries with the given name, and the given parameter values, and removes them if any exist. If the arguments do not match, then no action is taken. This action never fails.

RETRIEVE relation_name argument1 argument2 ... argumentN;
Information from the world model can also be accessed using the retrieve action. But retrieve action gets new values from the world model for the variable arguments regardless of the current value of the variables. Like fact, this action searches for the first world model entry, in this case matching only against the relation name. This action should be used carefully because, if the action is executed and it fails to get new values, the variable arguments will lose their values. This action succeeds if there is an entry with the given relation name in the world model, and fails otherwise.

TEST expression;

The action succeeds if the expression evaluates to true, otherwise it fails. Note that an expression is true if it has either a non-zero value or is a non-null string.

UPDATE (relation_name arg1 arg2 ... argN) (relation_name arg1 arg2 ... argM);
The system searches the world model for all entries with the same name and the same parameter values as given in the first relation and removes them if any exist. The second relation is then asserted in the world model. If no arguments are given in the first relation then all but one of the world model relations with the matching relation name are removed and the remaining relation is updated with the information given in the second relation. This action never fails.

WAIT goal_name parameter1 parameter2 ... parameterN;
wait actions cause the system to suspend execution of the KA until the specified goal is achieved. As with achieve goals, parameters can return values. This action cannot fail. wait goals are not currently implemented.

WHEN : action0 { action1; action2; ... actionN; };
The action0 (typically a test action) is executed and, if it succeeds, the sequence of actions action1, action2, ... actionN are executed. Use of this action simplifies programming many conditional branch situations. If more complex conditional branches need to be programmed, use the or construct.

WHILE : action0 { action1; action2; ... actionN;};
The action0 (typically a test action) is executed and, if it succeeds, the sequence of actions action1, action2, ... actionN are executed. When actionN has been successfully executed, action0 is again checked. This continues until eventually action0 fails, and the action after the while is then executed, or until one of action1, action2,... actionN fails, whereby the entire while action fails.

Example:

WHILE : TEST (> $x 10)

{

EXECUTE print $x;

ASSIGN $x (+ $x 1);

};

The name of the KA is simply for ease of human perusal and is not used at all during execution of the system. It is merely a label for the Knowledge Area.

The documentation slot may be used to store descriptive text of any type. Notes about special characteristics of the KA, a description of how the KA works, etc. can be placed here. It does not impact upon system execution in any way.

The purpose of a KA specifies the goal that successful execution of the KA body will satisfy. The syntax of the purpose is the same as that for a KA body achieve, maintain, or wait goal. A purpose may also be a query action.

During execution of PRS, this purpose will be matched against top-level goals (see Section 5), as specified by the user before the system is started, and against KA body actions that specify a goal or query. If the KA’s purpose matches, and the context is satisfied (as explained below), it is considered an applicable approach to solving the goal and may be intended (see below, in Section 10) and executed.

The context of a KA specifies exactly in which situations the KA may be useful. The context is checked when a KA is being considered for inclusion in a Set of Applicable KAs (the SOAK), a list of KAs that are applicable toward solving a goal. The context is also continually checked throughout the execution of a KA once the KA starts execution, to make sure that the KA is still applicable to the intended situation.

It is important to understand when expressions fail, and when they succeed. For example, failure for a fact predicate (for more information on predicates, see below) results from the inability of the system to find a correct match in the world model for the given world model relation and instantiated arguments. The fact action uses the instantiated arguments during matching and does not overwrite those values with new values. Care must be taken that variables used in facts in the context are not changed in the KA body to values that would cause the context to fail.

During SOAK generation, if the context check is not satisfied, the KA is not considered applicable to the situation and is dropped from consideration for execution. Also, if the context of a currently executing KA fails, the entire KA, and any of its subgoals, are deemed invalid and removed from the intention structure.

CONTEXT: FACT task_complete "False";

FACT task "Do Nothing";

An example of a KA context incorporating a primitive function is shown below. This example demonstrates how a primitive function can bind a value to a variable that is used later in the context (it can be used within the KA body too, of course). This example context, then, is satisfied when the distance between two points is less than 5.

KA {

PURPOSE: ACHIEVE example_completed $x1 $y1 $x2 $y2;

CONTEXT:

(calc_distance $x1 $y1 $x2 $y2 $distance);

(< $distance 5);

BODY:

EXECUTE print "Within 5 units.\n";

}

ACHIEVE goal_name parameter1 parameter2 ... parameterN :PRIORITY expression;
This predicate checks for the presence of the given goal in the system’s goal list. It uses the current variable values within the goal’s parameter list and checks for an exact match. If an exact match is found, the predicate returns true, otherwise it returns false.

FACT relation_name argument1 argument2 ... argumentN;
A fact acts as a predicate once variables in the fact action have values bound to them. This predicate tests to see if the given world model relation with the given arguments exists in the world model. It returns true if one is found, false otherwise.

RETRIEVE relation_name argument1 argument2 ... argumentN;
The retrieve action acts as a predicate when found in a context expression or a test action (also in such cases as the test component of a while or do action). This predicate tests to see if there are any world model entries with the given relation name and the correct number of arguments. If a world model entry exists, this predicate returns true, otherwise it returns false.

Note that a side-effect of this predicate is to bind new values to the variables if a world model match is found. Any variable bindings in the retrieve predicate will be replaced.

The priority field of a KA is optional and specifies the priority of the instantiated KA. The default KA priority is 0 when it is not specified. The priority can be any valid expression including an expression with variables as in the following example.

The details of how the KA priority and the goal priority are interpreted will be explained in Section 10.

The effect section is identical in format to a KA body, but is used to represent a simplified and abstracted procedural representation of the real procedure. There are no limitations or constraints upon the content of the effect section with respect to a KA body. Everything that can be done within a KA body can be done within the effect section.

This section of a KA is executed when UM-PRS is run in simulation mode (see Section 9.2). World model updates and subgoaling are the typical KA actions contained in the effect section. Loops and branches are constructs that we foresee as being abstracted out of the body when writing the effect section. If the effect section is empty, the interpreter considers the KA to have succeeded.

An example KA with an effect section is shown below:

KA {

NAME:

"Test Interpreter in simulation mode"

PURPOSE:

ACHIEVE sim_done;

CONTEXT:

FACT test_done "False";

BODY:

EXECUTE print "\nNormal execution started.\n";

EXECUTE print "Simple subgoaling.\n";

ACHIEVE system_initialized;

UPDATE (system_init) (system_init "True");

EXECUTE print "More complex subgoaling.\n";

ACHIEVE indirect_communicated "Execution started indirect.\n";

EFFECT:

ACHIEVE system_initialized;

UPDATE (system_init) (system_init "True");

ACHIEVE indirect_communicated "Simulation started indirect.\n";

}

When a KA fails due to its context failing, it and all of that KA’s subgoals are deemed to have failed. In this case, the failure sections of each of the failed KA’s subgoals are executed, from the "leaf" KA (the KA for the goal at the bottom of the subgoal stack — i.e., that which does not have a subgoal itself) back up to the failed KA. The following KAs demonstrate the use of failure sections and, when executed, will illustrate how the failure sections are executed when a KA’s context fails.

GOALS:

ACHIEVE testing_done;

FACTS:

test_done "False";

force_failure 0;

//------------------------------------

// KA

//------------------------------------

KA {

NAME:

"Test Interpreter on subgoal failure"

DOCUMENTATION:

"Test Interpreter on subgoal failure"

PURPOSE:

ACHIEVE testing_done;

CONTEXT:

FACT test_done "False";

BODY:

EXECUTE print "Just before top level ACHIEVE.\n";

OR

{

ACHIEVE communicated "In Failure branch1.\n";

ACHIEVE subgoal_failed1;

}

{

ACHIEVE communicated "In branch2.\n";

};

}

//------------------------------------

// KA

//------------------------------------

KA {

NAME:

"Subgoal to failure1"

DOCUMENTATION:

"Intermediate level subgoal failure."

PURPOSE:

ACHIEVE subgoal_failed1;

CONTEXT:

FACT test_done "False";

FACT force_failure 0;

BODY:

EXECUTE print "In subgoal_failed1\n";

ACHIEVE subgoal_failed2;

}

//------------------------------------

// KA

//------------------------------------

KA {

NAME:

"Subgoal to failure"

DOCUMENTATION:

"Make sure subgoal failure 'works'."

PURPOSE:

ACHIEVE subgoal_failed2;

CONTEXT:

FACT test_done "False";

BODY:

EXECUTE print "In subgoal_failed2\n";

OR

{

ACHIEVE communicated "In Failure branch1 #2.\n";

ACHIEVE ka_failed;

}

{

ACHIEVE communicated "In Failure branch2 #2.\n";

ACHIEVE ka_failed;

};

FAILURE:

EXECUTE print "\nsubgoal_failed2 failed.\n\n";

}

//------------------------------------

// KA

//------------------------------------

KA {

NAME:

"Simply fail."

DOCUMENTATION:

"Make sure that KA fails"

PURPOSE:

ACHIEVE ka_failed;

CONTEXT:

FACT test_done "False";

BODY:

EXECUTE print "Just before failure.\n";

UPDATE (force_failure) (force_failure 1);

EXECUTE print "Just after failure. Should never get here.\n";

FAILURE:

EXECUTE print "\nka_failed failed.\n\n";

}

//------------------------------------

// KA

//------------------------------------

KA {

NAME:

"Communicate the text to the user"

DOCUMENTATION:

"Print and speak the text"

PURPOSE:

ACHIEVE communicated $TEXT;

CONTEXT:

FACT test_done "False";

BODY:

EXECUTE print $TEXT;

FAILURE:

EXECUTE print "\ncommunicated failed.\n\n";

}

An example of a complete UM-PRS program which includes a CYCLE (which simply maintains and prints out the number of times the interpreter has cycled) is shown below:

GOALS:

ACHIEVE cycle_tested;

FACTS:

test_done "False";

system_init "False";

cycle_number 0;

CYCLE {

RETRIEVE cycle_number $N ;

EXECUTE print "\nCycle#" $N "\n";

UPDATE (cycle_number $N) (cycle_number (+ $N 1));

}

KA {

NAME:

"Test CYCLE"

PURPOSE:

ACHIEVE cycle_tested;

CONTEXT:

FACT test_done "False";

BODY:

EXECUTE print "\nNormal execution started.\n";

UPDATE (system_init) (system_init "True");

WHILE : TEST (== 1 1)

{

EXECUTE noop;

};

}

GOALS:

ACHIEVE cone_demo :PRIORITY 10;

MAINTAIN obstacles_avoided;

Top level goals are persistent goals. That is, they are pursued until they are satisfied. In contrast, goals within KA bodies are not persistent (see Section 3.2.1).

The intention structure maintains information related to the runtime state of progress made toward the system’s top-level or "system" goals. The system will typically have more than one of these top-level goals, and each of these goals may, during execution, invoke subgoals to achieve lower-level goals. With the current implementation, a goal that is being pursued may be interrupted by a higher priority goal and then later resumed (if possible). To manage this, the intention structure keeps track of which top-level goals are being pursued, and which action in each KA is currently being executed.

When a goal gets suspended, due to a higher level goal becoming applicable, the current state of execution of the current goal is stored. When the suspended goal becomes the highest priority goal again, it is "reactivated". There is nothing unusual in the reactivation process. It is identical to normal execution. However, due to the possibility that the world model has been changed during the pursuit of other goals, the contexts of the resumed top-level goal and its subgoals may no longer be valid. If they are all still valid, execution resumes at the exact place where it was suspended. However, if the context of one of the KA’s context fails, that KA, and any of its subgoals, is considered to have failed. This is the normal behavior for KAs whose context fails. See Section 3.6 for more details.

#include "user.h"

int main(int argc, char* argv[])

{

return um_prs(argc, argv);

}

Each primitive action referenced in a KA body must have a corresponding C++ or C language function that can be directly executed. An interface function that deals with converting UM-PRS variables to/from C/C++ representation must be specified for each primitive function.

The UM-PRS system is composed of a C++ library which can be linked directly to the user-defined interface functions and primitive executable functions. In order to make it easy for the user to define interface functions, we provide users with a set of constructs defined in the "user.h" header file. Thus, "user.h" should be included in every interface function file. The details of how to make a UM-PRS application are demonstrated in the "example" directory. Users are advised to copy the "Makefile" and the example C++ file and to modify it for their applications.

All the interface functions have the same parameters as defined as follows:

#define PRIMITIVE_FUNCTION(name) \

Value name(long arity, ExpList* args, Binding* binding=0)

#include "user.h"

double user_priority_evaluation(double goal_priority, double ka_priority)

{

return goal_priority * ka_priority;

}

int main(int argc, char* argv[])

{

// Point to the user priority evaluation function

// Uncomment if such functionality is desired.

// program.priority_evaluation_function_hook = user_priority_evaluation;

return um_prs(argc, argv);

}

Figure 1: User priority evaluation function.

The primitive function interface arguments are: arity, which specifies the number of arguments to the primitive function; args, which are the arguments of the primitive, and binding, which holds the variable bindings associated with the passed arguments. A simple print interface function is shown in Figure 2.

Finally, the user needs to define a list of primitive UM-PRS function name and the corresponding C++ interface function as follows:

FunctionNamePair user_function_list[] = {

{ka_print_args, "print_args" },

{ka_get_dead_reckoning, "get_dead_reckoning" },

{ka_calc_euclidean_distance, "calc_euclidean_distance" },

{0, 0 }

};

PRIMITIVE_FUNCTION(ka_print_args)

{

if (arity < 0) return Value::False;

ExpListIterator arg_list(args);

Expression* exp;

// Go through each argument and print it individually

for(exp = arg_list.get_next(); exp; exp = arg_list.get_next())

cerr << exp->eval(binding);

// This primitive function has successfully completed.

return Value::True;

}

Figure 2: Primitive function that gets passed arguments.

PRIMITIVE_FUNCTION(ka_get_dead_reckoning)

{

int status, x, y;

// If there aren't enough arguments then this

// primitive function fails.

if (arity < 2) return Value::False;

ExpListIterator arg_list(args);

// This parameter will be used for return values.

Expression* robotx = arg_list.get_next();

Expression* roboty = arg_list.get_next();

// determines robot's position

get_dead_reckoning(&x, &y);

// Bind the newly determined values to return arguments

binding->set_value(robotx,Value(x));

binding->set_value(roboty,Value(y));

// This primitive function has successfully completed.

return Value::True;

}

Figure 3: Primitive function that returns values.

PRIMITIVE_FUNCTION(ka_calc_euclidean_distance)

{

double dist;

double euclidean_distance(Point* p1, Point* p2);

// If there aren't enough arguments then this

// primitive function fails.

if (arity < 3) return Value::False;

ExpListIterator next_exp(args);

// Get the parameters for the primitive function.

// These can be int, float, char *, void *

void* p1 = (void *) next_exp()->eval(binding);

void* p2 = (void *) next_exp()->eval(binding);

// This parameter will be used for return values.

Expression* distance = next_exp();

// call the actual function that performs the calculation

dist = euclidean_distance((Point*) p1, (Point*) p2);

// Bind the result to the return (3rd) argument

binding->set_value(distance,Value((float) dist));

// This primitive function has successfully completed.

return Value::True;

}

Figure 4: Primitive function that gets and returns values.

where the first entry is the name of the interface function and the second entry is the name used within a Knowledge Area.

Currently there are several predefined primitives. They are defined below:

print expression1 ... expressionN;
This primitive function permits output to cout (typically the screen). The expressions can be any valid expression, including constant values (e.g. numbers, strings), variables, calculations, etc. Most formatting characters, such as "\n", "t\", etc. (as in C/C++ languages) are permitted.

sleep sleeptime;
This primitive pauses for the number of seconds indicated by the integer argument sleeptime.

get_time $var;
This primitive returns the value of the Unix time() function in the given variable argument. An example is shown below.

noop ;
This primitive function performs no action at all, simply returning successfully.

read_integer var_list;
This primitive function accepts the input of one or more integer numbers from the user.

read_float var_list;
This primitive function accepts the input of one or more floating point numbers from the user.

read_string var_list;
This primitive function accepts the input of one or more strings from the user. The current maximum length of each string is fixed, and is defined in the file "primitive.h" as READ_STRING_INPUT_SIZE.

remove_ka string_list;
This primitive function will cause all of the KAs with a name that matches one of the given strings to be considered invalid, and therefore no longer applicable to be selected for execution. The example given below shows how to remove KAs with the name "Test CYCLE" (defined in Section 4).

Before UM-PRS is executed, the UM-PRS library must be built and linked with the compiled primitive action functions and primitive action interface functions as described above in Section 8. Then, when UM-PRS is invoked, it needs to know where to look for the KA library, the world model, and the system’s goals. The file containing this information is specified as a command line argument. UM-PRS parses the text from the file argument and creates internal storage representations for all of the information before proceeding with execution. If there are any parsing problems, UM-PRS will indicate this with appropriate error messages. UM-PRS will then begin to execute KAs until either there is an error (such as an error in a primitive action) and/or all of the system’s goals have been achieved or have failed.

UM-PRS recognizes the following runtime options for debugging purposes.

UM-PRS’s first activity is parsing the initial definitions of the World Model, system Goal List, cycle procedure, and KA Library. If there are any problems found while parsing, UM-PRS will output a line of text of the form:

<filename>:error:<line#> (<character#>):parse error

There are currently two modes of execution for UM-PRS. The standard mode of operation is for the KA body procedure to be executed. This is the default. Another mode of operation executes the effect section of a KA. This section of a KA was introduced to facilitate plan prespecification, simulated forecasting, or similar functionality. UM-PRS is placed in simulation mode by the using the run-time switch "-S" (see above). See Section 3.8 for complete details on the effect section of a KA.

The UM-PRS interpreter is responsible for selecting and executing Knowledge Areas based upon the goals and context of the current situation. Associated with the interpreter is the Intention Structure, a run-time stack (stacked based upon subgoaling) of instantiated KAs, and the Goal List, the set of the system’s current top-level goals. The interpreter operates using the basic cycle shown below in pseudocode:

while (1) {

execute_cycle();

generate_SOAK(soak);

// If a new SOAK, or if last SOAK was non-nil, add it to the

// SOAK list

if (soak || previous_soak) soak_list(add,level++);

// Continue to top of loop and see if a meta-level SOAK is generated.

if (soak) { previous_soak = soak; continue; }

// If no new KAs were relevant

if (!previous_soak) {

if (all_goals_achieved) exit;

else {

// Execute something (in the leaf KA) in the intention structure.

if (intention_structure.execute() == FAILED) {

intention_structure.unintend();

level = 0;

soak = 0;

}

}

}

else {

// Randomly select one of the new KAs of highest priority

// and add it to the intention structure

intention_structure.intend(soak.highest_priority_random());

// Execute something (in the leaf KA) in the intention structure.

if (intention_structure.execute() == FAILED) {

intention_structure.unintend();

level = 0;

soak = 0;

}

}

}

In our current implementation, the interpreter selects one KA based on the priority of the goal and the KA when there are multiple elements in the SOAK. When a goal is posted the optional goal priority (Section 3.2.1) is evaluated and associated with the goal. If no explicit goal priority is specified, its default value becomes 0.

The priority of the instantiated KA in SOAK is the sum of the goal priority (Section 3.2.1) and the KA priority (Section 3.7) in default. If users want to override the default priority evaluation function, please refer to Section 7. Note that since the KA priority of the KA is calculated at runtime, the same KA with different bindings can have different priorities.

The interpreter selects the KA with highest priority and, if there are multiple KAs with the highest priority, it selects one among them randomly.

UM-PRS is very reactive to changes in the environment. When a new fact about the world is recorded in the world model through sensing, communication, or internal conclusions, the UM-PRS interpreter will look for KAs that are applicable to the new situation. Likewise, if a new goal (or goals) is added, UM-PRS looks for applicable KAs to satisfy the new goal(s). In either case, UM-PRS selects one of the applicable KAs, intends it (places it on the intention structure), and then executes something in the active "intention".

NOTE: The current implementation of the intention structure and UM-PRS interpreter only permit single threaded execution of intentions; i.e., only one top-level goal can be pursued at a time. If one goal becomes active due to a change in the context and partly executed, any progress toward a second goal that was being executed before that will be lost.

We performed some tests on various plan constructs of the UM-PRS planning system to get an idea of the performance of the system. Some of the results that we have come up with are summarized below.

We ran several tests to determine the execution performance of loops. In the first test timed the execution of a while loop running through 100,000 iterations. We then did the same for a do loop. The body of each loop was simply a variable decrement action. And, to get an idea of the performance with nested loops, we then ran a test where a 1000 iteration do was nested within a 100 iteration while. The results are shown below.

The results show that do loop execution is quite a bit slower than while loops. Based upon these results we are looking into our implementation to improve the performance of do loops.

In these tests we executed a KA which subgoals to another KA which subgoals, etc. to 10 levels. The eleventh KA calls a trivial primitive function. Shown below are the results for varying numbers of iterations of calling the top-level subgoal.

Interestingly, the results show a non-linear increase in the amount of time taken as the number of iterations increased; our expectations were that it would be linear. We are looking into why this is the case.

Although we have not yet done so, there are more experiments related to subgoaling that we plan on performing. We wish to determine the performance of the SOAK generation algorithm on large KA libraries with various characteristics. One test will be on a library that has a large number of KAs with the same purpose. Another test will be on a large KA library in which each KA has a different purpose. A further test will be to determine the effect of context complexity on system performance.

The next tests explored the performance of executing KAs with branches. The table below shows a KA which iterates over and and or actions with 10 (ten) branches. Each branch consisted of a simple test action.

The results shown are roughly linear, as expected.

In this section we discuss those changes that we have made from the previous version. These are listed below:

In this section we describe any known shortcomings of the current version of the implementation. Please contact the authors if any problems are encountered that appear to be UM-PRS software bugs.