Plan.oz
Compile this file to create the "pickled functor" file Plan.ozf.
In the driver code, create a new planner class with:
MyPlanner = {New Plan.planner Fluents Actions}
Call member functions like this:
{MyPlanner exploreActions(Situation)}
functor
import
FD FS Search
Explorer
Inspector
Space
% Ozcar
% System
% Inspector
% Browser
export
Planner
define
% This function returns a deep copy of its input. The input can be
% any type data. Undetermined variables are copied as new cells. If
% an undetermined variable is a finite domain variable, then the
% copy will be constrained to the current domain of the input
% variable.
%
% This is needed because we sometimes want undetermined variables
% from the top-level space to participate in constraints in a
% subordinate computation space, but in general doing so would cause
% the subordinate computation space to be unstable. So we use this
% procedure to copy the top-level variable.
% TODO: Figure out a way to avoid the need for this function. It's
% incomplete, and it may in fact be impossible to write it to so
% that it works correctly in the most general cases, esp. in the
% presence of custom propagators.
%
proc {CopyDomains In ?Out}
if {FD.is In} then
Out :: {FD.reflect.dom In}
elseif {FS.var.is In} then
raise unimpl(debug:"Don't know how to copy FS domains yet.") end
elseif {Not {IsDet In}} then
Out = _ % Fresh variable
elseif {Record.is In} then
Out = {Record.map In fun {$ F} {CopyDomains F} end}
else
Out = In
end
end
% This is basically an "assert-like" function. If the predicate function
% P applied to value V is false, we raise an exception.
proc {Require P V}
if {Not {P V}} then
raise reqFail("Requirement {"#P#" "#V#"} failed.") end
end
end
% This function checks that D is a valid representation of a finite
% integer domain. The definition of the form of D is taken directly
% from the Mozart System Modules reference manual.
%
% We use this to verify some of the definition data for fluents.
fun {IsFDSpec D}
fun {IsSimpleSpec D}
fun {IsRangeDesc D}
fun {IsFDInt N}
{IsDet N} andthen
{IsInt N} andthen N >= FD.inf andthen N =< FD.sup
end
in
{IsDet D} andthen
case D
of Min#Max then {IsFDInt Min} andthen {IsFDInt Max}
[] N then {IsFDInt N}
else false
end
end
in
{IsDet D} andthen
case D
of nil then true
[] S|Dr then {IsRangeDesc S} andthen {IsSimpleSpec Dr}
[] S then {IsRangeDesc S}
else false
end
end
in
{IsDet D} andthen
case D
of compl(S) then {IsSimpleSpec S}
[] S then {IsSimpleSpec S}
else false
end
end
% This function returns a function which, when applied to a procedure
% argument, returns true if the procedure has arity N. (I.e. takes N
% arguments. We use this in conjunction with Require to verify data
% definitions for the planner.
fun {IsProcArity N}
fun {$ P}
{IsDet P} andthen {IsProcedure P} andthen {ProcedureArity P} == N
end
end
% FluentDefParsers take a fluent definition in the form of a record
% and returns a properly-formed fluent definition. The input fluent
% definition may omit certain fields, which will be filled in with
% defaults. Calculating the defaults up front allows the planner to
% work with predictably-formed fluent records, which simplifies
% the planner code.
%
% We also validate the input fluent definition. Any errors cause an
% exception to be raised. The thrown value is a record with label
% badFluentDef.
proc {MkFluent Def ?F}
% FluentDefParsers is a record of procedures used to generate the
% corresponding features of a fluent record from the fluent
% definition.
FluentDefParsers =
fdp(name: fun {$ Def} {Require IsAtom Def.name} Def.name end
desc: proc {$ Def ?V}
V={CondSelect Def desc {AtomToString Def.name}}
{Require IsString V}
end
init: fun {$ Def}
Temp={CondSelect Def init FD.inf#FD.sup}
in
if {IsFDSpec Temp} then fun {$} {FD.int Temp} end
else
{Require {IsProcArity 1} Temp}
Temp
end
end
infer: proc {$ Def ?V}
% If infer is not defined, default to "true"
Infer={CondSelect Def infer true}
in
{Require IsDet Infer}
if {IsProcedure Infer}
andthen {ProcedureArity Infer} == 2 then
V=Infer
else
{Require IsBool Infer}
if Infer then
% If infer is true, provide a function which copies
% the value from the previous situation.
V=fun {$ SPrev} {Value.'.' SPrev Def.name} end
else
% Otherwise, provide a do-nothing funtion.
V=proc {$ _ _} skip end
end
end
{Require {IsProcArity 2} V}
end)
in
% Supply defaults and possible calculated values.
% Everything except the name can be defaulted.
try
F = {MakeRecord fluent [name desc init infer]}
{Record.forAllInd F fun {$ L } {FluentDefParsers.L Def} end}
catch reqFailed(Msg)
then
raise badFluentDef(def:Def debug:{VirtualString.toString Msg}) end
[] E then
raise badFluentDef(def:Def debug:E) end
end
end
% This procedure is similar to MkFluent, but for action records.
proc {MkAction Def ?A}
% ActionDefParsers is a record of procedures used to generate the
% corresponding features of a fluent record from the fluent
% definition.
ActionDefParsers =
adp(name: fun {$ Def} {Require IsAtom Def.name} Def.name end
desc: proc {$ Def ?V}
V={CondSelect Def desc {AtomToString Def.name}}
{Require IsString V}
end
pre: proc {$ Def ?V}
V={CondSelect Def pre fun {$ _} true end}
{Require {IsProcArity 2} V}
end
effect: fun {$ Def}
{Require {IsProcArity 2} Def.effect} Def.effect
end
effector: fun {$ Def}
{Require {IsProcArity 2} Def.effect}
Def.effect
end
inputs: proc {$ Def ?V}
V={CondSelect Def inputs fun {$ _} var() end}
{Require {IsProcArity 2} V}
end
)
in
try
A = {MakeRecord action [name desc pre effect effector inputs]}
{Record.forAllInd A fun {$ L } {ActionDefParsers.L Def} end}
catch reqFailed(Msg)
then
raise badFluentDef(def:Def debug:{VirtualString.toString Msg}) end
[] E then
raise badFluentDef(def:Def debug:E) end
end
end
% This procedure makes a fresh situation record from a previous situation
% and a list of well-formed fluent records.
proc {MkSitRec SitPrev Fluents ?Sit}
Sit = {MakeRecord
situation
prev|{Map Fluents fun {$ fluent(name:N ...)} N end}}
Sit.prev = SitPrev
{ForAll Fluents
proc {$ fluent(name:N init:Init ...)}
Sit.N = {Init}
end}
end
% Given lists of well-formed fluent and action records, and a
% situation record, this function returns a procedure that can
% be used to search for "decision records" that reflect an
% action choice, action input parameter choices, and an expected
% consequent situation. The function computes and returns the decision
% record as its sole argument, thus it conforms to the expectations
% of the Mozart's constraint-solving system for a solver script.
fun {MkActionChooser Fluents Actions Sit}
% This is the procedure that we return. It will have access to the
% fluents, actions, situation that were passed into
% MkActionChooser. You can think of this as being similar to
% instantiating a template in C++, except that it happens at
% run-time, and we return the resulting procedure as a first-class
% value.
proc {$ R}
% This procedure helps us track our progress for debugging
% purposes.
proc {NoteProgress Str}
Temp
in
if {IsVirtualString Str} then
Temp = {VirtualString.toString Str}
else
Temp = Str
end
{Assign R.phase {StringToAtom Temp}}
end
% Here we take a list of fluents, and apply their inference rule
% speculatively to the current situation. This is "speculative"
% because if a rule conflicts with what we already know about a
% fluent, then we simply ignore that rule. This can happen, for
% instance, if we are trying to infer the state of a fluent in a
% hypothetical situation after we've applied an action that
% affected the fluent. The inference rules are simply intended
% to reflect what we think will happen to a fluent in the
% absence of any active influences.
proc {InferFluents Sit Fs}
% Infer current fluents from prev, speculatively.
case Fs
of nil then skip
[] F|Fr then
{NoteProgress "Inferring fluent "#F.name}
% Try to apply each of the inference axioms in a temporary
% child space. If the space fails, just ignore it. Otherwise
% merge the results into this space.
local
S= {Space.new
proc {$ _} {Value.'.' Sit F.name} = {F.infer Sit.prev} end}
in
case {Space.askVerbose S}
of failed then skip
[] succeeded(...) then _={Space.merge S}
[] suspended(...) then _={Space.merge S}
else
raise
error(
debug: {VirtualString.toAtom
"Fluent inference proc for "
#F.name#" caused bad space state."})
end
end
end
{InferFluents Sit Fr}
end
end
% This is an index into the action list. Here we define its
% domain to span from one to the length of the action list. At
% some point in the algorithm below, we distribute the solution
% search on the range of this variable.
AIndex = {FD.int 1#{Length Actions}}
in
% Build a new root record. Initially, the consequent situation
% is just a default situation, with no further information known
% about it. The "phase" field is used to track progress, it can
% be seen conveniently in the Inspector when working with the Explorer.
R = decision(
phase: {NewCell "Starting"}
situation: {CopyDomains Sit}
consequent: _
action: _
inputs: _)
R.consequent = {MkSitRec R.situation Fluents}
% Try to apply our inference rules to fill in more information about
% the current situation of the world. This is how we guess at what
% we don't know. Overly ambitious attempts to guess at fluent states
% could rule out actions that would actually be OK, but leaving
% fluents too undetermined could cause us to investigate or even choose
% actions that have a low chance of actually succeeding.
{NoteProgress "Inferring fluents."}
{InferFluents R.situation Fluents}
% Now choose an action. We simply distribute on the possible values
% for AIndex.
{NoteProgress "Distributing on action index."}
{FD.distribute naive [AIndex]}
R.action={Nth Actions AIndex}
% Now that we've selected an action, assert that it's precondition
% axiom is true (1). If not, then this thread (and its computation
% space) will fail.
{R.action.pre R.situation} =: 1
{NoteProgress "Action precondition passed."}
% Now get the inputs for this action. Some of these may simply
% be fluents, some may be entirely new values that are for all
% intents and purposes fluents, but are only created when we're
% considering the associated action. (This keeps the number of
% fluents in the model down to a bearable number, hopefully.)
% The "inputs" procedure of the action is responsible for
% creating a record containing all of the inputs, so it has wide
% latitude in deciding how to choose and constrain them. All
% inputs must be finite-domain variables.
R.inputs = {R.action.inputs R.situation}
{NoteProgress "Action inputs defined."}
% Now we distribute on the inputs. Execution after the distribution
% proceeds in alternate computation spaces with distinct combinations
% of input values. Depending on constraints set up by the action
% record's input procedure, some combinations may be illegal and will
% cause failure of those spaces. We then actually apply the action's
% effect axiom to the hypothetical situation and the current combination
% of inputs to compute the resulting hypothetical situation.
{NoteProgress "Distributing on action inputs."}
{FD.distribute naive R.inputs}
{R.action.effect R.consequent R.inputs}
{NoteProgress "Applied action effect axiom."}
end
end
% The Planner class is a convenient encapsulation of all the dirty
% details in this module. On creation of a Planner object, you must
% supply a list of fluent and action definitions, which will be
% validated. Then you can use the planner to investigate plans
% for various situations.
%
% TODO: Provide better debugging support by integrating better with
% the Explorer. Provide for a user-supplied solution evaluation
% procedure to direct branch-and-bound search strategies.
class Planner
feat
fluents
actions
meth init(F A)
self.fluents = {Map F MkFluent}
self.actions = {Map A MkAction}
end
meth mkSitRec(SitPrev ?Sit)
Sit = {MkSitRec SitPrev self.fluents}
end
meth chooseAction(Sit ?D)
[D] = {Search.base.one {MkActionChooser self.fluents self.actions Sit}}
end
meth exploreActions(Sit)
{Inspector.configure widgetTreeFont font(family: courier
size: 10
weight: normal)}
{Inspector.configure widgetTreeDisplayMode false}
{Explorer.object script({MkActionChooser self.fluents self.actions Sit})}
end
end
end