! RAP - Reactive Agent Planner for Inform ! Goalseeking Engine v 1.1, March 2000 ! ! Module maintainer: ! Nate Cull (culln@chchpoly.ac.nz) ! ! Revision history: ! 1.0 - RAP for TADS 1.0, first gmd.de release (rap10.zip), 1998 ! 1.1 - Inform port, code cleanup and documentation, March 2000 ! 1.2 - Inform cleanup and re-work, March 2004 ! ! General approach is based on a modification and simplification ! of the HAP reactive planning system as described in publically ! available white papers for the CMU OZ project ! ! Notes on my symbol naming convention: ! All globals are prefixed with Rap ! All constants are underscore delimited words, all uppercase ! All variables and functions are underscore delimited words, all lowercase ! All object classes are mixed case delimited words, leading uppercase ! All object instances are mixed case delimited words, leading lowercase System_file; ! Opcode values Constant RAP_NOP = 0; Constant RAP_BE = 1; Constant RAP_IF = 2; Constant RAP_DO = 3; ! Working queue ! ! These should strictly speaking be properties of a RapEngine object, ! but Inform's array support is weird and it looks easier all round to ! just make them globals. Ifndef RAP_QUEUE_MAX; Constant RAP_QUEUE_MAX = 255; Endif; Global rap_queue_length; Array rap_queue_parent --> RAP_QUEUE_MAX; Array rap_queue_plan --> RAP_QUEUE_MAX; Array rap_queue_step --> RAP_QUEUE_MAX; Array rap_queue_opcode --> RAP_QUEUE_MAX; Array rap_queue_token --> RAP_QUEUE_MAX; Array rap_queue_param1 --> RAP_QUEUE_MAX; Array rap_queue_param2 --> RAP_QUEUE_MAX; ! Return fields for rapGoal.get_plan() ! (since we can't return a list of multiple values in Inform, ! we're faking it by using global variables) Global rap_test_opcode; Global rap_test_token; Global rap_test_param1; Global rap_test_param2; ! Return fields for goalseek() ! (ditto) Global rap_answer_action; Global rap_answer_param1; Global rap_answer_param2; ! Internal state for the RAP engine ! copies of the initial parameters to goalseek(), ! mirrored as globals so other RAP functions can access them ! ! (These should strictly speaking be properties of a RapEngine object, ! but I'm not sure how fast Inform's object handling is so I'm using ! globals for everything. Also, these may be of use if we want to ! know what the last call to RAP was.) Global rap_trace_level; Global rap_target_actor; ! goalseek - main RAP API routine ! ! Purpose: attempts to find the most appropriate action to accomplish ! the given goal ! ! Inputs: my_actor - the object which is making ! this RAP search. Some actions ! and conditions may find this useful. ! my_condition - a rapGoal object ! my_param1 - plus two arbitrary parameters ! my_param2 - which make up the goal to achieve ! ! Outputs: stores the suggested action in rap_answer_ global variables ! the action will be RapNullAction if no action can be found ! returns true if an action is found and needed, false otherwise ! ! Algorithm: Constructs a breath-first search of the move tree each time ! the function is run, and returns when the first viable ! action is found. ! [ rap_goalseek my_actor my_condition my_param1 my_param2 goal_condition goal_param1 goal_param2 abort_plan num_steps current_step queue_pointer action_found current_goal current_plan ; if (rap_trace_level > 0 ) print "^rap: beginning search for ", (name)my_actor, ", wanting ", (name)my_condition, " ", (name)my_param1, " ", (name)my_param2, "."; ! Load the parameters into the globals rap_target_actor = my_actor; ! Load a default action in case we return without finding anything rap_answer_action = RapNullAction; rap_answer_param1 = false; rap_answer_param2 = false; ! Check if the goal has already been achieved, if so there's no need to search if (rap_trace_level > 1 ) print "^rap_goalseek: trace: checking condition^"; if (my_condition.istrue(my_actor, my_param1, my_param2)) { ! Return false, indicating that the actor needs to make no action if (rap_trace_level > 0 ) print "^rap: nothing to do^"; rfalse; } ! Clear the queue rap_queue_length = 0; ! Load the target goal onto the head of the queue rap_queue_parent --> 0 = 0; rap_queue_plan --> 0 = 0; rap_queue_step --> 0 = 0; rap_queue_opcode --> 0 = RAP_NOP; rap_queue_token --> 0 = my_condition; rap_queue_param1 --> 0 = my_param1; rap_queue_param2 --> 0 = my_param2; ! Expand the target goal into its subgoals, these will be what we search rap_expand_goal (0); ! Main loop: run through the queue, until we either: ! a) find an action ! b) run out of goals to expand ! c) run out of queue space ! ! What we're trying to do is this: ! ! for each unfulfilled goal (to begin with, the target goal), ! we produce a number of alternative plans to fulfil it. ! ! We examine each of these plans in parallel. ! ! Each plan consists of a number of steps (goals, followed by one action) ! which we examine *sequentially*. The first plan to return a viable action ! is (currently) considered to be the best one and is returned as the ! suggested action. IE, a breadth-first shortest-path search of the move ! tree. ! ! (This assumes that all actions are equally costly to the actor. In future ! versions we might attach a cost weighting to each action and keep going ! gathering a bunch of actions, then return the lowest-cost action or make ! a random selection). But this is the cheapest and simplest algorithm ! to start with). ! ! We use a queue to model this search. Each queue entry represents one ! plan being examined. As we iterate through each step for a queue entry, ! we update the 'step' counter in the queue array. If a step is an ! action, we 'fire' this action (ie, place it under consideration as a ! candidate for returning - in this implementation, that means we exit ! the search immediately). ! ! If a step is a goal that is fulfilled, we continue with the next ! step for this plan. ! ! If a step is a goal that is not fulfilled, but for which a plan exists, ! we expand it (add all its child plans to the queue), abort this plan ! and try the next plan in the queue. ! ! (Duplicate goals are detected and are not added onto the stack, otherwise ! we'd end up with circular references.) ! ! If a step returns a goal that is not satisfied and for which plans do not ! exist (or which we have indicated with the 'RAP_IF' opcode that we don't ! want to expand), then we abort this plan without expanding it. ! ! Eventually we will produce a viable action (ie, that can be run ! immediately), or we will run out of plans (or queue space) and fall off ! the bottom of the queue. In which case we return the default action that ! we loaded earlier (rapNullAction). queue_pointer = 0; action_found = false; while ((queue_pointer < rap_queue_length) && (action_found == false)) { queue_pointer++; if (rap_trace_level > 1) { print "^rap: starting queue pass for entry ", queue_pointer; } ! Read an entry from the queue, and convert it into an actual goal plan ! whose steps we can traverse. Note that the queue numbering is somewhat ! nonintuitive: until we've touched a freshly expanded queue entry, ! all it will have will be a parent and a plan number - we've got to ! lookup its *parent's* entry in the planbase to find out what goal ! it's trying to fulfil, and hence what steps we need to try. ! So we do that now, and cache it, rather than looking it up for each step. current_goal = rap_queue_parent --> queue_pointer; current_plan = rap_queue_plan --> queue_pointer; goal_condition = rap_queue_token --> current_goal; goal_param1 = rap_queue_param1 --> current_goal; goal_param2 = rap_queue_param2 --> current_goal; if (rap_trace_level > 1) print "^rap: got goal info^ current_goal=", current_goal, ", current_plan=", current_plan, ", goal_condition=", (name)goal_condition, ", goal_param1=", (name)goal_param1, ", goal_param2=", (name)goal_param2, "^"; ! Get the number of steps for this plan - the hard way, since there ! ain't no easy way. Asking for step 0 of plan X means we're asking ! for the number of steps in that plan. And of course, the result gets ! stuffed into the rap_test_ globals rather than returned nicely. num_steps = goal_condition.get_nbr_steps( rap_target_actor, goal_param1, goal_param2, current_plan ); if (rap_trace_level > 0) print "^plan ",current_plan, " has ", num_steps, " steps^"; ! Second loop: Loop through all steps for this plan, until either we hit ! something that makes us abort this plan (like an unfulfilled goal, ! or a fired action) or we fall off the end. It is possible and non-fatal ! to have a plan which does not contain any fireable actions, but simply ! is a set of conditions. It might not be useful, but it is logical and ! will be handled gracefully. It is not possible however to fire an action ! then keep executing further steps in a plan. I can't think of any ! situation where this would be useful or desired behaviour. abort_plan = false; current_step = 0; while ((current_step < num_steps) && (abort_plan == false)) { current_step++; if (rap_trace_level > 1) print "^rap: step ", current_step, "^"; ! Look up this step in the planbase. Same procedure as before. goal_condition.get_plan( rap_target_actor, goal_param1, goal_param2, current_plan, current_step ); if (rap_trace_level > 0 ) print "^rap: considering plan ", queue_pointer, ", step ", current_step, ", token=", (name)rap_test_token, ", p1=", (name)rap_test_param1, ", p2=", (name)rap_test_param2, ") "; ! Update our current plan entry in the queue with the step details rap_queue_step --> queue_pointer = current_step; rap_queue_opcode --> queue_pointer = rap_test_opcode; rap_queue_token --> queue_pointer = rap_test_token; rap_queue_param1 --> queue_pointer = rap_test_param1; rap_queue_param2 --> queue_pointer = rap_test_param2; ! Interpret the step we retrieved with a big old switch block switch (rap_test_opcode) { RAP_DO: if (rap_trace_level > 0) print "^rap: RAP_DO opcode - "; ! DO opcode - fire the action the quick and easy way, for now if (rap_trace_level > 0) print "firing^"; rap_answer_action = rap_test_token; rap_answer_param1 = rap_test_param1; rap_answer_param2 = rap_test_param2; action_found = true; abort_plan = true; RAP_IF: if (rap_trace_level > 0) print "^rap: RAP_IF opcode - "; ! IF opcode - this condition must be true, otherwise abort this plan ! and don't bother making it a goal !!! if (rap_test_token.istrue(rap_target_actor, if (rap_test_token(rap_target_actor, rap_test_param1, rap_test_param2) == false) { if (rap_trace_level > 0) print "not fulfilled^"; abort_plan = true; } else { if (rap_trace_level > 0) print "fulfilled^"; } RAP_BE: if (rap_trace_level > 0) print "^rap: RAP_BE opcode - "; ! BE opcode - this condition is a goal, so if it's not true then add all ! child goals of this one to the queue if (rap_test_token.istrue(rap_target_actor, rap_test_param1, rap_test_param2) == false) { ! Okay, the goal isn't true, so we're going to abort this plan abort_plan = true; ! and if this goal isn't already in the queue... if (rap_no_dupe_goals(queue_pointer)) { if (rap_trace_level > 0) print "expanding^"; ! ... expand it. rap_expand_goal(queue_pointer); } else { if (rap_trace_level > 0) print "duplicate^"; } } else { if (rap_trace_level > 0) print "continuing^"; } default: ! unknown opcode - if we got here, something's screwed up ! Probably either a broken get_plan() routine for a rapGoal ! or an internal error in the engine. Either way, give an error print "^warning: unknown opcode ", rap_test_opcode, " in condition ", goal_condition, ", plan ", current_plan, ", step ", current_step, ", ignoring.^"; } ! switch (rap_test_opcode) if (rap_trace_level > 1) print "^end of steps loop, current_step=", current_step, ", abort_plan-", abort_plan, "^"; } ! while ((current_step < num_steps) ... } ! while ((queue_pointer < rap_queue_length) ... ! We've finished the main loop by fair means or foul, ! so return the exit code and get out of here. if (rap_trace_level > 0 ) print "^rap: suggesting ", (routinename)rap_answer_action, " ", (name)rap_answer_param1, " ", (name)rap_answer_param2, ".^"; return action_found; ]; ! rap_expand_goal - internal RAP function, puts new goals on queue [ rap_expand_goal goal condition param1 param2 num_plans plan ; ! Look up goal x in queue array (because Inform arrays are pretty dumb, ! and we can't do this on one line). condition = rap_queue_token --> goal; param1 = rap_queue_param1 --> goal; param2 = rap_queue_param2 --> goal; if (rap_trace_level > 1) print "^rap_expand_goal: ^goal=", goal, ", condition=", (name)condition, ", param1=", (name)param1, ", param2=", (name)param2, "^"; ! First, we need the number of plans available for this goal. ! Note that the number of plans may vary depending on the goal's ! parameters, so we play it safe and give everything. num_plans = condition.get_nbr_plans(rap_target_actor, param1, param2); if (rap_trace_level > 0) print "^rap: expanding ", num_plans, " plans."; ! Loop through all plans for our calling goal for (plan = 1 : plan <= num_plans : plan++) { ! Check that we aren't falling off the end of the queue - ! if so, abort and return false, ie, some goals were lost ! The search can still continue however, since it's possible ! that we don't need the goals that were lost. All that will ! happen is that an action is not found. ! ! Show a warning anyway. if (rap_queue_length + plan > RAP_QUEUE_MAX) { print "^rap_expand_goal: warning: queue overflow, some plans ignored^"; rfalse; } ! Push a new entry onto the queue, indicating that: ! it is a child of our calling goal, and it is this plan number rap_queue_length++; rap_queue_parent --> rap_queue_length = goal; rap_queue_plan --> rap_queue_length = plan; rap_queue_step --> rap_queue_length = 0; rap_queue_opcode --> rap_queue_length = RAP_NOP; rap_queue_token --> rap_queue_length = false; rap_queue_param1 --> rap_queue_length = false; rap_queue_param2 --> rap_queue_length = false; } ]; ! rap_no_dupe_goals - checks if there are any duplicates of the specified goal ! returns true if the goal is the only one of its kind [ rap_no_dupe_goals goal queue_index dupe_condition dupe_param1 dupe_param2 ; dupe_condition = rap_queue_token --> goal; dupe_param1 = rap_queue_param1 --> goal; dupe_param2 = rap_queue_param2 --> goal; if (rap_trace_level > 1) print "^rap_no_dupe_goals: starting^ goal=", goal, ", condition=", (name)dupe_condition, ", param1=", (name)dupe_param1, ", param2=", (name)dupe_param2, "^searching: "; for (queue_index = 0 : queue_index <= rap_queue_length : queue_index++) { ! We can consider it a duplicate only if the token and both params match if ((queue_index ~= goal) && ((rap_queue_token --> queue_index) == dupe_condition) && ((rap_queue_param1 --> queue_index) == dupe_param1) && ((rap_queue_param2 --> queue_index) == dupe_param2)) { if (rap_trace_level > 1) print "^rap_no_dupe_goals: duplicates found, returning false^"; rfalse; } if (rap_trace_level > 1) print queue_index, ", "; } ! end of for loop ! if we fall off the end, it must be because no duplicates exist if (rap_trace_level > 1) print "^rap_no_dupe_goals: no duplicates, returning true^"; rtrue; ]; [ rap_set_step opcode token param1 param2 ; rap_test_opcode = opcode; rap_test_token = token; rap_test_param1 = param1; rap_test_param2 = param2; rtrue; ]; Class rapGoal with istrue [ actor param1 param2 ; print "^rap: undefined condition ", self, "^"; rfalse; ], get_plan [ actor param1 param2 plan step ; rfalse; ] ;