EUROPA2: User and Contributor Guide
Contents
1. YourObject helloWorld eq duration 10 meets object helloWorld met by object helloWorld All models will include Plasma nddl and PlannerConfig nddl Plasma nddl contains definitions for most common NDDL constructs PlannerConfig nddl 10 4 HELLO ROVER GETTING STARTED WITH PLASMA contains definitions for horizons and the maximum number of steps a planner can take before finding a plan or giving up The next section of the model defines the class YourObject Notice that we specify YourObject as a timeline Other options are object or resource YourObject contains a single predicate called helloWorld with no arguments helloWorld however has hidden variables to denote its duration the class it belongs to and a few other things helloWorld will be the only predicate that will describe the state of YourObject Finally the model contains a single rule for the predicate helloWorld It specifies that the predicate has a duration 10 and that it meets another predicate of the same time and that it is met by another predicate of the same type Meets and met by are taken from the Allen Relations and they are inverse of each other and mean that one predicate must be immediately followed by another and vice versa You can see all temporal relations that EUROPA 2 supports in Appendix 9 2 4 3 Creating an initial state In this section we ll go through the initial state file and explain2. met by Unstow a meets Position b Rules for Navigator Navigator At at is preceeded by a Going whose destination is location met by object Going go before eq go before to location at is followed by a Going whose source is location meets object Going go after eq go after from location Navigator Going going is preceeded by an At whose location is from met_by object At at_before eq at before location from going is followed by an At whose location is to 5 7 Advanced Rules 21 meets object At at after eq at after location to Select a path from those available between the 2 points we create a local variable p to contain all paths that match the from and to Path p eq p from from eq p to to h Consume units of battery assuming p cost is negative Should be based on path length starts Battery change tx eq tx quantity p cost 5 7 Advanced Rules In the the previous section we covered 1 basic rules meets met by contained by starts 2 constraints among parameters of predicates 3 commonAncestor constraint that is used when traversal of the object hi erarchy is required 4 local rule variables 5 existential quantification by creating a filter In this section we will cover other more advanced concepts such as conditional rules and universal quantification Assume now that we want to model a rover that can accept reques
3. active or inactive A token is active if commitment to the token being in the plan is made A token is inactive otherwise All token flaws that can be inferred from the partial plan and the model via configuration rules are represented as Inactive Tokens Figure 2 illustrates the states and transitions of tokens in EUROPA 2 A token is Active immediately when introduced by an actor external to the plan database as is the case with a goal G specified in an initial partial plan A token is initially Inactive when introduced by a configuration rule of the predicate of an Active Token As prescribed by CAPR 4 an inactive token corresponds to a token flaw which can be resolved by either merging with a matching Active Token or by choosing to use the resolver T via activation Merging is chosen to represent that the configuration rule is satisfied by an existing state that which is active and participates in merging Activation is chosen to represent that a new state is needed to satisfy the configuration rule 3 5 Planning Scheduling Decisions Planning scheduling decisions arise from flaws in the partial plan Flaws can be either unsatisfied configuration rules unordered tokens in objects if they have 8 4 HELLO ROVER GETTING STARTED WITH PLASMA specific ordering requirements or unbound variable assignments A planner is done when it has verified that all applicable configuration rules are satisfied A configuration rule is applicable when the
4. cerr All messages can then be enabled with DebugMessage enableA110 and an individual one can be enabled with DebugMessage msg msg gt enable An individual debug message can be looked up using msg DebugMessage findMsg file marker If this matches more then one existing debug message the first one found will be returned To find all messages in a given file e g 5 11 Debugging 35 zu K xL ZEITEN IN A A AE Figure 12 EUROPA 2 PlanWorks Temporal Extent View std list lt DebugMessage gt msgs DebugMessage findMatchingMsgs file amp msgs where the second argument is a empty zero length std string Note that msgs is not cleared emptied by this function only added to An empty string can also be passed for the file name so DebugMessage findMatchingMsgs amp msgs will have the same effect as msgs DebugMessage getAllMsgsO except the latter is currently a const reference to the internal list and thus runs much faster but cannot be modified In all cases individual messages will not appear in such lists unless the code in question where the debugMsg call appears has already been executed until then the info about the individual debug message simply isn t available 36 6 PLASMA SYSTEM ARCHITECTURE Removing this restriction would require the complete list of debug messages to be constructed at compile time similar to how the entire list of pa
5. can be done via a mechanism we call Plan Identification 8 In brief EU ROPA2 provides a set of standard conditions that candidate flaws have to pass in order to become flaws that must be resolved for planning to complete One of these conditions is a temporal variable condition that filters out all temporal variables thus temporal variables never appear as variables whose assignments need to be made Another way of controlling early vs delayed commitment can be done by specifying rules conditional on variable assignments A heuristic can then be used to determine when such variable assignments should be made and when subgoaling can occur 4 Hello Rover Getting started with PLASMA This section will demonstrate a simple example that takes an initial state and a model and runs a planner on them to produce a plan EUROPA2 does not include a GUI However you can use an adjunct project called PlanWorks to visualize a plan and step through the planning process once the planner has produced a plan This section will illustrate how to get started with EUROPA 2 4 1 Creating a Project 9 4 1 Creating a Project After successfully building EUROPA2 by following the instructions in the README and BUILDING files located in the PLASMA root directory you can create your own project by invoking makeproject with the name of your project as an argument in the PLASMA root directory This will create a direc tory with the name of your project t
6. in the destructor the m id should be removed When deleting references to ids call delete on the cast operator e g delete ConstrainedVariable ref Magic Numbers Define an enumerated type to handle number references instead of using magic numbers Classes Capitalize names of classes When composing names for classes cap italize the first letter of each word Declare a virtual destructor Pure Virtual Classes Declare a protected constructor Declare all functions pure virtual Methods Declare a method const where possible Do not return bare pointers or non const references If the caller can own a data structure that is to be populated in the callee create the data structure in the caller and then pass it by reference as an argument Avoid copying of data structures where possible Declare non primitive arguments as const references Return non primitive values as const references Error Checks 48 10 ACKNOWLEDGEMENTS Use checkError to express pre conditions Use checkError to express invariants Use checkError to express post conditions Avoid using non const functions in checkError tests Do not use assert Do not use Id isValid outside of checkError Do not write if Test checkError Check Write checkEr ror Test Check Debugging Output Use the Europa debugging output management system Do not
7. installed PlanWorks run it using ant This should bring the initial screen as shown in Figure 3 File New Bookmarks Desktop Windows Help Figure 3 EUROPA2 PlanWorks Initial Screen You ll see the screen with the following menus File Project PlugIn and Help the Windows menu will be disabled since there are no windows inside your PlanWorks workspace Click on Project and create a new project Then select your planning sequence which should be under your plans directory and will be a long name with a sequence number encoded in the name Figure shows the planning sequence screen Once you have loaded a sequence you ll see two panels SequenceQuery and SequenceStepsView The SequenceStepsView shows a histogram of each of the planning steps The first bar indicates the first step of the plan and the last bar the last step of the plan A yellow dot above the bar indicates that data is available for this step A red dot means that no data is available for this step The green dot means that the data is available and loaded The color of the dot changes when you decide to log only some steps or when you use the planner 5 10 Visualization of the plan and planning process in Plan Works 27 LITT Ty O TTT Figure 4 EUROPA2 PlanWorks Planning Sequence control Each bar is composed of three different colors The green color denotes the number of tokens the blue color denotes the number of variables and the sand color de
8. only those things that you re interested in viewing Click on the content filter window In Predicate type Navigator Going Then press Apply Filter You should see the timeline view restricted to the free Going tokens only with no tokens on any of the timelines That is because there are currently no inserted tokens on any timeline nav is the only possible one Figure 7 shows the timeline view with Going tokens only Now let s identify the Going token that we want to find out more information about The way to do this is to query for the token events that affected the token This will give us an idea of what happen throughout the lifetime of that 5 10 Visualization of the plan and planning process in Plan Works 29 b aPlanWorks PW_M_18 Plan Visualization of Project gt UGR File Project Planning Sequence Window Plug in Help La Sequenesquen for uncut LLY 2 LE Y LL SLT Y E ContentFilter for UserGuideRover step34 i y Where Constraint Transatted Key CONSTRAINT ALL C NOT Predicate Apply Query Y NOT Predicate T j ddl On Timeline NOT Time interval Star a v 107 Time Interval Start End 7 Merge tokens View all slotted free tokens 6 require e exclude Add Remove Apply Filter Reset Filter E Navigatorview of UserGuideR g x E TimelineView of UserGuideRover step34 ter ems Si Nav
9. the time at which token B ends NDDL syntax A after B A any B A before B A contained_by B A contains B A contains_end B A contains start B A ends B A ends after B A ends after start B A ends before B A ends during B A equal B A meets B A met by B A paralleled_by B A parallels B A starts B A starts_after B A starts_before B A starts_before_end B A starts_during B Constraints created B end lt A start none A end lt B start B start lt A start A end lt B end A start lt B start B end lt A end A start lt B end B end lt A end A start lt B start B start lt A end A end B end B end lt A end B start lt A end A end lt B end B start lt A end A end lt B end A start B start A end B end A end B start A start B end B start lt A start B end lt A end A start lt B start A end lt B end A start B start B start lt A start A start lt B start A start lt B end B start lt A start A start lt B end Here are the inverse relations 9 2 Appendix B Temporal Relations 45 NDDL syntax A after B A any B A before B A contained by B A contains B A contains end B A contains start B A ends B A ends after B A ends after start B A ends before B A ends during B A equal B A meets B A met by B A paralleled_by B A parallels B A starts B A starts_after B A s
10. Activate Collaboration Diagram call Entity purgeStarted delete rules engine delete plan database delete constraint engine call Entity purgeEnded NDDL 1 2 3 initialize type factories create plan database see above purge type factories CBPlanner create plan database or NDDL if using NDDL schema create Horizon create planner create open decision manager unless using default provided initialize horizon from planner config object run planner with step limitation from planner config object delete planner 7 2 Using and extending the CBPlanner 41 activate deactivate fleactivate specify Figure 17 Merge Collaboration Diagram e delete plan database or NDDL if using NDDL Schema PlanWorks e create planner but also create a PartialPlanWriter with all objects that you want to log e delete the PartialPlan Writer The particular set of steps will vary depending on your application One thing to consider is that the Schema and the factories are all static while you can have more than one plan database constraint engine etc As a general rule we enforce the relationships upon construction 7 2 Using and extending the CBPlanner 7 3 Custom constraints Let s say that you now require special constraints and have available a propa gation algorithm that knows and handles those constraints Assume that you now want to handle more general classes of constraints You can u
11. EUROPA 2 User and Contributor Guide Tania Bedrax Weiss Conor McGann Andrew Bachmann Will Edgington Michael Iatauro QSS Group Inc Computational Sciences Division NASA Ames Research Center Moffett Field CA 94034 1000 tania cmcgann bachmann wedgingt miatauro email arc nasa gov February 7 2005 Contents 1 Work In Progress 2 2 Introduction 3 23L Plan Services ois d aaa bod bd eene bob bs 3 2 0 EUROPA2 Design Goals 0 000000 0 4 221 Zbfheleueys gu pex ce Sese Td 4 212 2 Blexibility aac ads bd a ae Hh Be eg ond 5 2 2 37 Extensibility 5 1 5 aspe a ee wo of gon Ry RR Mele a 5 3 Concepts 5 3 1 Plans in Planning Scheduling and Execution 5 3 2 Model Based Planning e 6 3 3 Partial Plans States and Relationships 6 3 4 Token State Model o 7 3 5 Planning Scheduling Decisions 04 7 3 6 Early vs Delayed Commitment llle 8 4 Hello Rover Getting started with PLASMA 8 4 1 Creating a Project sc ade wee ode dt aba o SUA 9 4 2 Building a simple model o 9 4 3 Creating an initial state o en 10 4 4 Running the planner eee 11 2 1 WORK IN PROGRESS 5 Developing Your Own Model In NDDL 5 1 Rover The Robotic Geologist 5 2 Locations and Paths 2s Did Instruments 4 m xg ee xeu uw xuPeee ES oid Batteries eso ELE ee USE e i etu 0 0 ROVS 2 35
12. Planner to work on the current partial plan In this case changes are also made in response to queries and operations on the Plan Database In the last figure planning technology is deployed for plan execution A partial plan may be used by an Executive for execution In such a scenario the partial plan is updated throughout execution The Executive may employ incomplete search to refine the partial plan as it goes A Planner may be employed to repair a plan or develop a refinement of the plan as the mission progresses In each of the cases described clients i e Planner User Executive leverage the services of a common server the Plan Database 3 2 Model Based Planning A Model expresses laws that govern a particular domain of interest A model for EUROPA 2 usually contains descriptions of entities in the system and rela tionships between them that allow a planner scheduler to infer conditions that must be satisfied in order to arrive to a solution to a problem based on that model Domains and problem instances are described in EUROPA 2 in NDDL A typical NDDL description will contain a set of classes predicates and con figuration rules Classes represent properties of the world that may or may not evolve over time predicates with variables represent state descriptions and configuration rules represent relationships between state descriptions that must hold the laws of the domain 3 3 Partial Plans States and Relationships A Pa
13. RVAL CLOSED inf 1 Your bject helloWorld Key 57 INT INTERVAL CLOSED O 0 INT INTERVAL CLOSED 1000 1000 YourObject helloWorld Key 5176 INT INTERVAL CLOSED 1001 inf Merged Tokens Rao kk INT INTERVAL CLOSED inf 9 YourObject helloWorld Key 101 INT_INTERVAL CLOSED 10 10 INT INTERVAL CLOSED inf 19 YourObject helloWorld Key 148 INT_INTERVAL CLOSED 20 20 INT INTERVAL CLOSED inf 979 Your bject helloWorld Key 5140 INT INTERVAL CLOSED 980 980 INT INTERVAL CLOSED inf 989 13 Your bject helloWorld Key 5192 INT INTERVAL CLOSED 990 990 Finished You ll notice that the file shows the resulting state of the objects declared in the initial state You ll notice also that there are two inactive tokens one that falls before the first token in object and another that falls after the last token in object These are tokens that fall outside of the horizon and are therefore not flaws of the plan which is why they remain inactive Notice also that there s a list of merged tokens Some of these tokens have unbound variables These are variables that were not decided before the planner decided to merge the token Once a token is merged its variables are no longer affected by propagation for efficiency reasons 5 Developing Your Own Model In NDDL In this section you will learn how to develop your own model in NDDL We will show most of t
14. ameters for full treatment of resources representation see 7 l initial capacity the initial capacity of the resource level limit min the minimum level that the resource is allowed to reach level limit max the maximum level that the resource is allowed to reach 2 3 4 production rate max the maximum production rate per unit of time 5 production max the maximum production overall 6 consumption rate max the maximum consumption rate per unit of time 7 consumption max the maximum consumption overall When creating a specific type of resource one can call the constructor of a resource super with specific values for these parameters to set the type of resource For example if Battery is a consumable resource we would write the following in the model class Battery extends Resource Battery float initial capacity float levellimitmin float level limit max super initial capacity level limit min level limit max 0 0 0 0 MINUS INFINITY MINUS INFINITY Note that we use the special constants MINUS_INFINITY and PLUS INFINITY to indicate that there are no restrictions on the amount that is consumed overall or the rate at which it is consumed 5 5 Rovers Rovers are composed of two kinds of instruments a Pan Cam which is an instru ment and a RAT which is a stowable instrument A rover must move between locations In order to track the rover s position we c
15. ating all objects in your system you must close the database Since EUROPA 2 is at its core a dynamic constraint satisfaction system it needs to know the complete set of entities before it can reason with them Reasoning is suspended while the database is not closed Once closed there is no way to open it Finally you must specify the tokens that you know must be present in the plan In this example we specify a single token initialToken of type hel loWorld that must be present on some object in this case there s only one object We also specify that it must start at time 0 via the eq constraint which is identified as an equality constraint in the assembly 4 4 Running the planner Now that you understand the model and the initial state can you guess what the plan should look like Let s see the planner should plan for a horizon betwen 0 and 1000 The initial state specifies that there s a single object object with a single token initialState of type helloWorld that starts at time 0 Since helloWorld has duration 10 which we know from the model and since helloWorld must meet and be met_by another helloWorld token we can begin to hypothesize that the end result will be an object full of helloWorlds all abutting each other How many Well we should see 100 of them since each has duration 10 To see this in action let s run by invoking jam jProject in the jPr
16. ation is useful as it allows systems to avoid incurring costs for components that are not required EUROPA 2 also provides a language to customize the system for new domain models Further more heuristic and flaw specifications are also provided An open API ensures flexbility in how EUROPA 2 is integrated 2 2 3 Extensibility EUROPA2 is highly extensible As new problems are encountered or new algorithms are developed there are many ways to integrate new capabilities as specialized components e g constraints propagators resources This is essential for success in research and mission deployments The content of this guide is laid out as follows We begin with an explana tion of the concepts underlying EUROPA 2 addressing its role as an embedded technology within a planner and its underlying paradigms for representation and reasoning We then switch gears to get the reader up and running with a particular assembly of EUROPA 2 that is included with the distribution In this section the reader will solve a prepared planning problem with EUROPA 2 without really understanding much about how it happened Following this we seek to build up some understanding with a tutorial like exposition of model de velopment and problem solving with EUROPA 2 s primary modeling language NDDL Having spent some effort working on the application of EUROPA 2 we turn to its underlying architecture This section gets under the hood to pro vide an unde
17. ces for planning and scheduling applications In CA PS 2005 Submitted for Publication 5 Ari K Jonsson et al Planning in interplanetary space Theory and prac tice In AIPS 2000 6 Nicola Muscettola et al Remote agent to boldly go where no AI system has gone before Artificial Intelligence 1998 7 Tania Bedrax Weiss et al Formalizing resources for planning In CAPS Workshop on PDDL Italy 2003 8 Tania Bedrax Weiss et al Identifying executable plans In CAPS Work shop on Plan Execution Italy 2003 9 Jeremy Frank and Ari K Jonsson Constraint based attribute and interval planning Journal of Constraints 2003 10 ILOG Ilog solver User manual July 1996 Version 3 2 11 LA Nesnas A Wright M Bajracharya R Simmons T Estlin and Won Soo Kim Claraty An architecture for reusable robotic software In Proceedings of the SPIE Aerosense Conference 2003 9 Appendices 9 1 Appendix A NDDL Language Reference class predicate int float string enum extends concurrent precedes object start end duration state time new goal rejectable activate specify constrain close 44 9 APPENDICES 9 2 Appendix B Temporal Relations In NDDL two tokens can be constrained in several simple ways including with the following abbreviations for several commonly used constraints In the examples A and B are tokens A start is therefore the time at which token A starts similarly B end is
18. change tx eq tx quantity 20 Camera Shoot 4 contained_by Navigator At atc eq atc location view meets object ShootRequest s0 eq s0 view view starts Battery change tx eq tx quantity 100 5 8 Recap 23 Finally we illustrate the use of universal quantification by showing how it is possible to quantify over all objects assuming there s a fixed number of it that is known at start time Assume the navigator has numerous instruments and you want to impose a constraint that says that all instruments must be in state StandBy whenever the navigator is in state Going You can either enumerate all instruments and impose the constraint on each one or you can say so with a shorthand rule as follows Navigator Going met by object At at before eq at before location from meets object At at after eq at after location to Select a path from those available between the 2 points Path p eq p from from eq p to to Pull juice from the battery Should be based on path length starts Battery change tx eq tx quantity p cost Ensure all instruments are in standby Rover myRover eq myRover nav object if myRover 1 ensure that the object has been bound to a singleton Instrument instruments commonAncestor instruments this object myRover instrument on rover foreach i in instruments contained by Instrument StandBy s impose constraint between Going and Standby eq s obj
19. der to see the entire data you can bring up an overview window Right click on the background of the Constraint Network view Select the Overview Window A small windows showing the entire data that can be displayed in this view will pop up The rectangle shows the data currently in view The Constraint Network view allows you to view all variables and consraints and their relationships to each other Figure 11 shows the Constraint Network View with the Overview window Let s open the Temporal Extent view on step 15 Scroll down until you see token Going with key 145 The top arrows that are above the line and pointing down show the range for the start time The bottom arrows that are beneath the line and pointing up show the range for the end time Mousing over the arrow will show you the time In this view you can show the timescale line which will help you view the events that happen before at and after that time 32 5 DEVELOPING YOUR OWN MODEL IN NDDL xL SUT Figure 9 EUROPA2 PlanWorks Token Network View with Going only with Rule Instance You can bring this line up by right clicking on the background of the view and selecting Set Time Scale Line You should see a red line appear wherever you had your mouse last That is also the current method to move the time scale line Figure 12 shows time 35 5 11 Debugging Another useful tool for debugging your models and planners is logging We have extensive logging that y
20. e the following include UserGuideRover nddl PlannerConfig plannerConfiguration new PlannerConfig 0 1000 500 Location lander new Location 0 0 lander Location rock1 new Location 9 9 rock1 Location rock2 new Location 1 6 rock2 Location rock3 new Location 4 8 rock3 Location rock4 new Location 3 9 rock4 Allocate paths Path p1 new Path Very Long Way lander rock4 2000 0 Category low Path p2 new Path Moderately Long Way lander rock4 1500 0 Category medium 5 10 Visualization of the plan and planning process in Plan Works 25 Path p3 new Path Short Cut lander rock4 400 0 Category high Allocate Rover Battery battery new Battery 1000 0 0 0 1000 0 Rover spirit new Rover battery close Establish the initial position for spirit goal Navigator At initialPosition initialPosition start specify 0 Starts at the beginning of the horizon initialPosition location specify lander Initial position is lander Establish a goal to shoot an image at a location sometime before the experiment that follows goal Camera ShootRequest image image filtering specify true image view specify rock4 image length specify 10 leq image start 49 leq 0 image start Establish a goal to position an instrument at a location goal Stowable_Instrument Position experiment experiment start specify 50 experi
21. eR RU eue E S RR eee 2 0 Basic Rules cu 4 4 oot be b 4E Shed RN 5 5 Advanced Rules c6 aa a a ts TS DiS RECAP a a a aca loge blige lah Gide deg a poh a eh ae e ot aA 5 9 Formulate and solve a planning problem 5 10 Visualization of the plan and planning process in PlanWorks Dell DEBUTA E rs NA eu uer atone eS halal ae Aes ok 6 PLASMA System Architecture 7 Customization and Extension 7 1 Configuration and Assembly o 7 2 Using and extending the CBPlanner 7 3 Custom constraints 2 lee ee 7 4 Custom propagation ue EESESAASLISeG e 7 5 Building modelspecializations llle 7 6 Custom rule implementations less 7 7 Specialized domains 20020500004 7 8 External data integration lee 7 9 Listeners and Loggers e e 7 10 Integration to Plan Works o e 8 Contributing to EUROPA 2 9 Appendices 9 1 Appendix A NDDL Language Reference 9 2 Appendix B Temporal Relations 9 3 Appendix C Constraint Library Reference 9 4 Appendix D Test Language Specification and Use 9 5 Appendix E Coding Guidelines 10 Acknowledgements 1 Work In Progress 13 13 14 15 16 17 18 21 23 24 32 36 38 38 41 41 42 42 42 42 42 42 42 42 43 43 44 46 46 46 48 This manual is still work in progress Here is a preli
22. ect i 5 8 Recap The entire model described above can be found under UserGuideRover nddl in the same directory as this user guide We have introduced the following concepts and illustrated them with examples in the UserGuideRover model 1 class 2 enum 3 float int string 24 5 DEVELOPING YOUR OWN MODEL IN NDDL e inheritance predicates predicate parameter constraints basic rules meets met_by contained by starts constraints among parameters of a predicate So OO cS UON S SEM commonAncestor constraint that is used when traversal of the object hi erarchy is required 10 composition 11 rules 12 guards 13 local variables 14 Using existential quantification filtering and binding 15 Using universal quanitifcation iteration over objects 5 9 Formulate and solve a planning problem Let us assume we re given a problem with a lander and four rocks with their corresponding coordinates Furthermore let s assume we re given three paths a very long path a moderately long path and a short cut Let s assume that there is a single rover called spirit that carries a battery and the default instruments We re interested in finding a plan where spirit is initially at the lander and it has to take an image of rock4 and place an instrument at rock4 Furthermore assume that our planning horizon is 0 to 1000 and that we re hoping to find a plan within 500 steps The initial state would look something lik
23. ed the technology to a broader range of planning techniques e g POCL planning 2 1 Plan Services EUROPA 2 provides the following services e Domain modeling for describing planning domains e Plan representation for updating partial plans Constraint propagation for propagating the consequences of updates to plans and determining violations Subgoaling for generating consequences of commitments in the plan e Flaw definition for specifying flaws from a partial plan e Decision management for generating and resolving flaws e Plan assessment for determining plan completeness 4 2 INTRODUCTION Each of these services can be used independently or in conjunction to build applications by creating an assembly which composes the services needed Please see Section 7 1 for more information EUROPA 2 provides the New Domain Description Language NDDL which deviates substantially from DDL in that it provides an object oriented syntax It is also compiled instead of interpreted NDDL provides syntax for describing objects timelines resources predicates rules variables and constraints It also provides facilities like inheritance and containment to describe complex objects Please see Section 5 for more information on NDDL Plan representation is a service provided by the Plan Database much as it was in EUROPA The Plan Database responds to plan modification operations by updating the partial plan or invoking specialized components to u
24. elect TokenNetwork View Double click on the Going token to expand and follow the expansion one level up and one level down This will give you an idea of its parent and its subgoals Then right click on Battery Change token and select the RuleInstance View This will bring up the rule code in a separate window This is useful when you re debugging your model as well as your planner Figure 9 shows the Token Network View just described If you have questions about the resource levels and want to view the resource profile you can click on Step 34 which should show the effect of the resources on the final plan The resource profile view shows the resource envelope and the limits imposed The transaction view shows all transactions to date Right click on the transaction in the middle row and bring up the Navigator view to display information about the transaction You ll see that Rule 8 is responsible for this transaction Click on Rule 8 and you should see the Going token with key 145 Figure 10 shows the Resource Profile and Resource Transaction windows for the last step 5 10 Visualization of the plan and planning process in Plan Works 31 Figure 8 EUROPA2 PlanWorks Token Query Let s open the Constraint Network view and let s see what constraints are acting on the variables of the Going token Click on every variable from left to right You ll have to scroll to get to the other variables since the view expands beyond your window In or
25. ere we talk about extending the object model 7 6 Custom rule implementations Here we talk about writing custom rules and we highlight that there s no mech anism to hook these rules up to NDDL 7 7 Specialized domains Here we discuss the type factory 7 8 External data integration 7 9 Listeners and Loggers 7 10 Integration to PlanWorks We discuss in this section how we integrate with PlanWorks We mention the PlanWorks cfg and the PlannerControl object and how PlanWorks can be used to query the sql database 8 Contributing to EUROPA 2 This section should have guidelines for how to contribute to the code base Where to submit it to how to contact the primes how to ask for help etc It should also reference the coding guidelines appendix REFERENCES 43 References 1 John Bresina Ari J nsson Paul Morris and Kanna Rajan Mixed initiative constraint based activity planning for mars exploration rovers In Proceed ings of 4th International Workshop on Planning and Scheduling for Space IWPSS 2004 2 John Bresina Ari Jonsson Paul Morris and Kanna Rajan Activity plan ning for the mars exploration rovers In Proceedings of the 15th Interna tional Conference on Automated Planning and Scheduling ICAPS 2005 3 D Dvorak R Rasmussen G Reeves and A Sacks Software architecture themes in jpl s mission data system In IEEE Aerospace Conference 2000 4 Andrew Bachmann et al EUROPA2 Plan database servi
26. hat is parallel to the PLASMA directory In it you ll find the following files Jamrules Jamfile Project Main cc jProject initial state nddl Project model nddl and ppw config EUROPA 2 uses Jam instead of make to build its files Jamrules and Jamfile are both part of the build system Jamrules specifies some variables and establishes dependencies with EUROPA2 Jamfile specifies the main program and its dependencies ppw config is a file that contains configuration options for PlanWorks Plan Works is a plan visualization system that can be installed along with EUROPA 2 to aid in understanding and debugging jProject initial state nddl contains the initial state or problem description and Project model nddl contains the model or domain description Both files contain descriptions in the NDDL language Finally the Project main cc contains the main program that creates an as sembly configuration of EUROPA 2 components and plans based on the given initial state and model files 4 2 Building a simple model In this section we ll go through the model file and explain it in detail Your model file should look like this include PLASMA NDDL core Plasma nddl include PLASMA NDDL core PlannerConfig nddl Obrief Place holder class with a single predicate class Your bject extends Timeline predicate helloWorld Predicate with no arguments h brief A simple rule to force a repeated cycle
27. he NDDL constructs but please refer to Appendix 9 1 for the complete list 5 1 Rover The Robotic Geologist We use a planning domain loosely based on the MER mission to show the ser vices provided by EUROPA2 We assume the application in question is one of producing daily activity plans for operation of a robotic planetary surface geologist we call Rover Rover is a mobile robot equiped with a range of instru ments to sample and study a geological site We will focus on the panoramic imager PanCam A Rover has a battery on board and can replenish its energy levels using solar power A Rover will be given activities to travel to a specific location deploy an instrument at that location and perform an experiment It will also be given information from the terrain For simplicity purposes we assume that the terrain is represented by a euclidean grid and that locations are indentified with two coordinates We also assume that paths between locations are fixed and that the Rover can only move between locations if there is a path between them Furthermore the Rover can only access those locations that it can reach without draining the battery The Rover includes a number of components that can be operating concur rently For example the Pan Cam can be tracking targets while the Rover is driving The Rover also imposes mutual exclusion constraints on components for instace the rock abrasion tool RAT must be stowed while Rover is moving Furthermo
28. he following class Instrument predicate Position Location rock int position speed eq position speed duration i predicate Positioned class Stowable Instrument extends Instrument int stow speed int unstow speed Stowable_Instrument int _stow spd int unstow spd stow_speed _stow_spd unstow_speed _unstow_spd j predicate Stow predicate Unstow predicate Stowed predicate Unstowed Stowable instruments will inherit the predicates Position and Positioned from Instrument since these are the only members of the class Note that predicates can have argument variables such as position_speed from the Po sition predicate Predicates can also impose constraints by definition on its arguments whether they re implicit such as duration or explicit such as po sition speed In this case we equal the corresponding speeds to the duration of each of the Position Stow or Unstow predicates 5 4 Batteries The Rover has a main battery that is solar powered A battery has state that is represented by numerical quantities and as such is represented in NDDL as a resource type In NDDL one can represent resources with different proper ties If we assume that the battery cannot be replenished we say that the battery is a consumable resource 7 Resources have a default constructor and 5 5 Rovers 17 can be initialized with the following par
29. hose to model the nav igation component separately The navigation component will be modeled in NDDL as follows class Navigator predicate At Location location predicate Going Location from Location to neq from to 18 5 DEVELOPING YOUR OWN MODEL IN NDDL The Navigator component indicates that the Rover can either be At a location or Going from one location to another Furthermore a Rover can only move between different locations as indicated by the constraint neq from to This constraint can appear in the predicate definition because it refer ences only variables that are members of the predicate If you want to include constraints between things other than predicate arguments whether explicit or implicit such as duration or object you must do so in a rule We ll show how when we describe rules in Section 5 6 Finally we can describe a Rover in the following way class Rover Navigator nav Instrument pancam Stowable Instrument rat Battery battery Rover Battery r nav new Navigator pancam new Instrument rat new Stowable_Instrument battery r 5 6 Basic Rules We are now in a position to write the rules governing the state transitions for Instruments and Navigators Let s first go through the rules 1 In order to position an instrument the navigator has to be at the desti nation 2 Placing an instrument consumes 20 units of the battery 3 I
30. igator Going Navigator Going Stowable Instrument Stow Camera ShootRequest key 400 key 126 key 313 key 770 Figure 6 EUROPA 2 PlanWorks Timeline and Navigator View token To do this identify token 145 in the spirit nav timeline Then bring up the token query results by entering the token key 145 in the Sequence Query window Identify first the Sequence Query window It should be long and thin and near the top of your workspace The options on the window should show Steps Where Constraint Transacted Key CONSTRAINT_ALL Instead of Where Constarint Transacted select Where Token Transacted and enter the key 145 in the key field then press Apply Query This will bring a window with the set of transactions that apply to the Going token 145 Figure 8 shows the results of the transaction query Notice that this window shows that the token was created in step 0 and activated in step 14 and inserted in step 15 Notice that in step 14 it is also added to an object There is only one object that could accept the Going since our model has a single rover so there is a single Token Added to Object transaction Let s find out next who mandated the creation of the Going token and what subgoal rules are acting upon it In order to do so we should bring up the 30 5 DEVELOPING YOUR OWN MODEL IN NDDL Figure 7 EUROPA 2 PlanWorks Timeline View with Going only Token Network View Right click on Step 14 and s
31. it in detail Your initial state file should look like this include lt Project gt model nddl Create a planner configuration instance in PLASMA Horizon Start Horizon End MaxPlannerSteps PlannerConfig plannerConfiguration new PlannerConfig 0 1000 500 Sample object YourObject object new YourObject Close the the PLASMA Database no more objects can be created close Now place your goals here goal Your0bject helloWorld initialToken initialToken start specify 0 Starts at beginning of the horizon The planner should take it from here Your initial state will always include the model it refers to It is possible to break up a model into several files and include them all at this point Alterna tively you can include only those parts of the model that are relevant for this initial state Next you need to create an instance of a PlannerConfig object and give it a start time and end time of the planning horizon and the number of steps to use as a bound during planning 4 4 Running the planner 11 Next you should create object instances of your classes In this case ob ject is an instance of YourObject It is possible to attach static properties to objects in the form of variables If you want to create different object instances with different properties you may specify a constructor for the object that takes in the different properties as argument Once you have finished cre
32. ively we can use a class to define locations and annotate locations with their properties Furthermore we don t have to express in the model how many locations we ll have it can be specified in a problem instance In this case we would write the following class Location int x int y string label Location int x int _y xX X y Y label anonymous j Location int x int y string _label xX X y label _label j j Notice that a location has three static properties x coordinate y coordinate and a label Notice there are two constructors one that takes in a label on construction and the other that assigns anonymous to the label It is often useful to assign arbitrary data to domain elements Domain elements that are described with static data only are called static and don t evolve over time Locations are examples of static data 5 8 Instruments 15 Paths are also static domain elements Let s assume that paths have a name to identify them a cost and the two locations it links We can describe paths in the model in the following way class Path string name Location from Location to float cost Path string name Location from Location to float cost name _name from from to _to cost _cost i Notice that this class is composed not only of primitive types but also of user defined types i e Location So far we have introduced the following pri
33. ment destination specify rock4 Want to get to rock4 The plan we re looking for will contain the steps required to get the stowable instrument from the stand by state to the positioned state Furthermore spirit s navigator will move from the lander to rock4 and its camera will take a picture of rock4 with a filter 5 10 Visualization of the plan and planning process in PlanWorks EUROPA 2 includes logging facility to transfer data about the planning process to a visualization tool called PlanWorks PlanWorks reads the data into a set of mysql tables and then produces a visualization of each of the planning steps PlanWorks can be configured to load all steps at once or only a subset of the steps A subset is useful when debugging large problems Furthermore PlanWorks can be used in planner control mode which allows a user to load steps during the planner execution Each set of steps is called a sequence Each sequence can be queried and viewed differently depending on the menu options We will walk you through some of the steps that we have found useful when visualizing EUROPA 2 plans For instructions on how to build PlanWorks please refer to the PlanWorks 26 5 DEVELOPING YOUR OWN MODEL IN NDDL documentation PlanWorks README For detailed instructions on how to operate PlanWorks please refer to PlanWorks GETTING STARTED More de tailed instructions on how to visualize your plan can also be found in PLASMA HELLOWORLD Once you have
34. minary list of things that we need to do 1 Review organization if reader doesn t know anything about EUROPA he she may be lost in the translation 2 Describe entities and relationships in the system possibly include an en tities diagram explaining the relationships 3 Describe mapping from planning into constraints 4 Describe planning decisions and how they translate to changes in the plan database 5 Describe extensions and external hooks 2 Introduction EUROPA2 is the next generation of the Extensible Universal Remote Op erations Architecture Like the CLARATy robotics control architecture 11 MDS 3 or ILOG 10 EUROPA2 is a component based software library for representation and reasoning with plans and schedules Our goal in develop ing EUROPA2 is to provide a fast flexible extensible reusable technology platform for building planning and scheduling applications suitable for space exploration EUROPA 9 5 which has been the core planning technology for a vari ety of NASA relevant research and mission applications A notable example is MAPGEN 1 2 the ground based daily activity planning system for the Mars Exploration Rover mission EUROPA in turn is derived from HSTS which was the planner for the Remote Agent 6 EUROPA2 builds on the legacies of EUROPA and HSTS and provides improvements in performance expressivity reasoning capabilities flexibility extensibility and modularity which has open
35. mitive types int float string We have also introduced enumerations Any class can contain a member of an enumerated type Say that paths were classified into difficulty levels depending on the obstructions along the way Let s say that we have a total of 5 difficulty levels low low medium medium medium high and high We would modify the description above to include the category in the following way enum Category low low medium medium medium high high class Path string name Location from Location to float cost Category level Path string name Location from Location to float _cost Category level name name from from to _to cost cost Category level _level 5 3 Instruments Instruments have state that can evolve over time There are two classes of instruments Instruments that can be stowed for protection from the elements 16 5 DEVELOPING YOUR OWN MODEL IN NDDL and instruments that are permanently exposed This example shows how we can aggregate the common properties of all instruments into a class and then use inheritance to derive the more specific class of stowable instruments All instruments can be positioned but only stowable instruments can be stowed and unstowed Furthermore we will assume that the speed that an instrument can be stowed and unstowed with varies depending on the kind of instrument The speed of placement will depend on the location In the model we would write t
36. n order to unstow an instrument the navigator cannot be moving thus it has to be At some location 4 Unstowing is possible only if the instrument was stowed and after unstow ing the instrument will be unstowed 5 Unstowing consumes 20 units of battery 6 In order to stow an instrument the navigator cannot be moving thus it has to be At some location 7 Stowing is possible only if the instrument was positioned we don t want to allow unstowing and stowing for no reason and after stowing the in strument will be stowed 5 6 Basic Rules 19 8 Stowing consumes 20 units of battery 9 Stowed is preceeded by a Stow and followed by an Unstow 10 Unstowed is preceeded by an Unstow and followed by a Position 11 At is preceeded and followed by a Going such that the preceeding Going s destination is the source of At and the successor Going token s source is the source of At 12 Going is preceeded by an At such that the location of at is the from of Going and Going is also succeeded by an At such that the location of at is the to of the Going 13 Going between a to and a from is only allowed if there exists a path p between the to and the from 14 Going consumes as much battery as the cost of the path Rules that apply to the same predicate can be aggregated into the same rule For instance the rules above in the model would appear as Rules for Instrument Instrument Position make sure it is at the desti
37. nation during the execution of Position contained by Navigator At at eq at location destination ensure that both at and position refer to the same object Rover rovers commonAncestor at object this object rovers consume battery starts Battery change tx eq tx quantity 20 Rules for Stowable_Instrument Stowable Instrument Unstow make sure it is at some location during the execution of Position contained by Navigator At at ensure that both at and unstow refer to the same object Rover rovers commonAncestor at object this object rovers unstow is followed by unstowed and preceeded by stowed meets Unstowed a met by Stowed b consume battery 20 5 DEVELOPING YOUR OWN MODEL IN NDDL starts Battery change tx eq tx quantity 20 Stowable_Instrument Stow make sure it is at some location during the execution of Position contained by Navigator At at ensure that both at and stow refer to the same object Rover rovers commonAncestor at object this object rovers unstow is followed by stowed and preceeded by position meets Stowed a met by Position b consume battery starts Battery change tx eq tx quantity 20 Stowable_Instrument Stowed stowed is followed by unstow and preceeded by stow met by Stow a meets Unstow b Stowable_Instrument Unstowed unstowed is followed by position and preceeded by unstow
38. ng planner as a standard client component though many applications develop their own clients The Decision Manager uses a view specification to manage the set of flaws for a client Please refer to the API documentation which can be generated by typing jam documentation in the top level directory To view the API documentation point your browser to the documentation html index html file at the top level directory Figure 13 EUROPA2 Architecture Diagram Helps to understand the interaction among components May want to use a simple example model possibly cut down from k9 1 Creating an Object Token activation Token deactivation Constraining a Token Freeing a Token Binding a Variable N 0 oO PF WwW m Freeing a Variable 38 7 CUSTOMIZATION AND EXTENSION Figure 14 EUROPA 2 Chronological Backtracking Planner Architecture Dia gram 8 Copying a plan database 7 Customization and Extension 7 1 Configuration and Assembly EUROPA 2 provides the capability to pick and choose components and config ure them based on application needs For example assume that you have an application that requires constraint reasoning services You may want to use only the Constraint Engine In this case you can create your own assembly where you allocate a Constraint Engine and instantiate a problem based on a problem description that you re given or using the ConstraintEngine Con straint and Variable APIs directly You can similarly con
39. notes the number of constraints This gives visual feedback as to the proportion of tokens variables and constraints in each step of the plannning process Right click on any column in the step view you ll see a set of menus Con straint Network View DB Transaction View Decision View Resource Profile View Resource Transaction View Temporal Extent View Timeline view and Token Network View as shown in Figure 5 Now let s get some information from the plan Let s focus on a Going token that takes spirit from the lander to rock4 Let s click on the last step and bring up the timeline view You can get more information about the Going token by right clicking on it and bringing up the Navigator view You ll see the token in the center of the view with its variables beneath it and the rule that is responsible for it s existence on the top You can find the parent token by 28 5 DEVELOPING YOUR OWN MODEL IN NDDL Figure 5 EUROPA 2 PlanWorks Step Menu clicking on the rule You ll see the token Navigator At appear in blue It is blue because that is the color of the Nav timeline You will also see the other Going token appear which also results from appylying rule2 Figure 6 shows the Timeline and Navigator View Since there s too much information and we are looking for the Going token why don t we limit the view to show only Going tokens We can do this by using the Content Filter The content filter allows you to restrict the view to
40. nsible to ensure services can be enhanced to meet the needs of research or mission applications 2 2 1 Efficiency EUROPA 2 has produced significant gains in speed over EUROPA The primary contributors to the improvement arise from 1 Fast interfaces and specialized implementations the ability to tune implementations using inheritance provides speed improvements in key areas such as operations on domains 2 Efficient merging EUROPA 2 provides an algorithm to handle merging operations that disables redundant constraints arising in the plan database 3 Incremental re laxation when relaxing a variable EUROPA 2 relaxes only variables reachable through the constraint graph 4 Direct support for static facts EUROPA2 uses objects to capture static facts Objects can be referenced through vari ables We provide a pattern for existentially quantifying objects By contrast EUROPA used timelines with a single predicate to capture this information incurring a high overhead through inefficient merging 2 2 2 Flexibility EUROPA2 is highly customizable Support for resources may be ommitted if a problem does not require resources If a problem does not require compatibil ities e g a scheduling problem the rules engine can be omitted If temporal constraints are not important in a problem the temporal propagator may be re moved and or replaced with the default propagator Only required constraints need to be registered This form of customiz
41. ny Foo tokens exist or the planning behavior whether or not a backtrack message occurred and asserts something about it Assertions are preceeded by a specification of when the assertion must be true They are grouped into tests that can be further organized into super tests Files containing collections of tests and assertions are converted into XML and then compiled into Aver instructions which are executed at run time See the API documentation for further information on Aver See also the Aver specification in Section 9 4 6 PLASMA System Architecture Figure 13 describes the internals of the EUROPA 2 Plan Database operating as a server to one or more clients The server is an assembly of EUROPA 2 compo nents integrated for the needs of the particular application The Plan Database provides a set of plan services of the server at the abstraction level of primitives 37 in CAPR i e tokens transactions constraints resources variables The Con straint Engine and related components propagate constraints among variables and detect violations The provided constraints and propagators can be freely integrated or omitted The Rules Engine reacts to changes in the partial plan ie token activation and variable binding The Schema is the in memory store for the domain model It is used by the plan database to enforce type restric tions and by the rules engine to match and execute compatibilities EUROPA 2 includes a chronological backtracki
42. oject root directory If you haven t already built EUROPA 2 this should trigger a build This command will also trigger a build of your main program You ll see a target called jProject g rt and a file with the output plan called RUN Project planner g rt Project initial state xml output Your output file should show the object with a sequence of helloWorld tokens lying between 0 and 1000 Your output file should look like this we ve replaced some of the output by Found a plan at depth 299 after 299 nodes PlannerConfig plannerConfigurat ion kkk kkk kkk k kk kk k k Your bject objectoceokoookoookoolokoooloookolookoelok INT INTERVAL CLOSED O 0 YourObject helloWorld Key 22 Merged Key 101 INT INTERVAL CLOSED 10 10 INT INTERVAL CLOSED 10 10 YourObject helloWorld Key 41 12 4 HELLO ROVER GETTING STARTED WITH PLASMA Merged Key 148 INT INTERVAL CLOSED 20 20 INT INTERVAL CLOSED 20 20 Your bject helloWorld Key 85 Merged Key 200 INT INTERVAL CLOSED 970 970 Your bject helloWorld Key 5020 Merged Key 5140 INT INTERVAL CLOSED 980 980 INT INTERVAL CLOSED 980 980 YourObject helloWorld Key 5072 Merged Key 5192 INT_INTERVAL CLOSED 990 990 INT_INTERVAL CLOSED 990 990 YourObject helloWorld Key 5124 INT INTERVAL CLOSED 1000 1000 End Timeline Object k Inactive Tokens kkk kkk kkk ad k k add ok k k ok ok K INT INTE
43. ou can configure through a file called Debug cfg This file must exist in the same directory as the executable or the debug information will not be logged Debug information is by default redirected to std cout You can change that by using DebugMsg setStream EUROPA 2 code is instrumented with debug messages of the form debugMsg marker token lt lt tokenId lt lt created 5 11 Debugging 33 zu E LLL i ANTH TET Figure 10 EUROPA2 PlanWorks Resource Profile and Transaction View which produce output like this TokenNetwork cc 6277 token id 56 created if and only if the marker is found in the Debug cfg file or debugging has been enabled in code The Debug cfg file format is defined according to the following are line comment characters and their scope ends at the end of line You can enable marker debug messages by file or all messages in a file or all messages matching the marker accross all files as in the following examples file marker comment file comment marker comment Each non comment and non empty line enables all matching debug messages including any that have the given marker string as any substring of their own marker 34 5 DEVELOPING YOUR OWN MODEL IN NDDL Figure 11 EUROPA2 PlanWorks Constraint Network View with Overview To enable debug messages in code the stream to write them to must be assigned DebugMessage setStream std cerr to send them to std
44. pdate parts of the partial plan Constraint propagation for instance is a service provided by the Constraint Engine and is in charge of responding to updates to constraints and variables triggered by the plan modification operations The Rules Engine is in charge of subgoaling also in response to plan modification operations Flaw definition decision management and plan assesment services are pro vided by the CBPlanner module The CBPlanner module implements a chrono logical backtracking planner that resolves all flaws in the partial plan except for temporal variable assignments as described in the literature 8 4 The philosophy underlying EUROPA 2 is to acknowledge up front that no one size fits all when it comes to which techniques to use and which capabilities to employ Consequently EUROPA 2 is engineered to allow people to take just what they need discard what they do not and integrate extensions to suit their particular requirements in a straighforward manner The design strategy is to focus on a core framework defininig the principal abstractions and interactions induced by our underlying paradigm We then provide concrete components to allow particular assemblies to be defined 2 2 EUROPA 2 Design Goals To meet the needs of missions and research projects the design of EUROPA 2 must be 1 Efficient to ensure low latency for operations and queries 2 Flex ibile to ensure services can be selected and flexibly integrated 3 Exte
45. put debugging output into stdout or stderr Documentation Use doxygen style comments with the javadoc style keywords brief etc Enforce emacs macros Class descriptions file descriptions parameters method return val ues errors Documentation is required for header files recommended for imple mentation files 10 Acknowledgements This research was supported by NASA Ames Research Center and the NASA Intelligent Systems program
46. r s inverse Note also the need for explicit bounds in most of the equivalencies due to Europa s relations being based on e g before or at the same time rather Equivalent Europa Relation A equal B A before 1 Inf B A after 1 Inf B A meets B A met_by B A contained by 1 Inf 1 A contains 1 Inf 1 Inf 1 A parallels 0 0 Inf 1 B A parallels 0 0 1 Inf B A parallels Inf 1 0 0 B A parallels 1 Inf 0 0 B unsupported as a single rela unsupported as a single rela 46 9 APPENDICES than Allen s relations being strictly before and the lack of explicit support for the last two Allen relations Europa II s additional flexibility does allow them to be expressed though more verbosely as the constraints themselves E g Allen Relation NDDL Constraints A overlaps B o LessThan A start B start LessThan B start A end LessThan A end A inverse overlaps B io LessThan A start B end LessThan B start A end LessThan B end 9 3 Appendix C Constraint Library Reference 9 4 Appendix D Test Language Specification and Use 9 5 Appendix E Coding Guidelines General Practices Ensure you declare variables and methods in their narrowest scope If you declare a static variable inside a non static method double check that the method should not be static and also double check that the variable should not be a member of the class We discourage writing code in header file
47. rameter constraint functions is presently done at compile time However the calls DebugMessage enableA11 DebugMessage disableA11 DebugMessage readConfigFile istream amp is are not restricted to existing messages as they store the patterns that are presently enabled and when a new message is created that matches any of the enabled patterns it is immediately enabled and therefore prints its mes sage immediately after being created as part of the debugMsg macro The method DebugMessage enableMatchingMessages file marker adds the appropriate pattern to this internal list of enabled patterns which is checked immediately for existing debug messages and also when a new debug message is created There is no corresponding disableMatchingMessages in the current imple mentation but that could be very tricky or costly at run time to implement for cases like DebugMessage enableA11 DebugMessage disableMatchingMsgs marker DebugMessage disableMatchingMsgs file DebugMessage enableMatchingMsgs marker since there is no explicit list of files or markers mentioned in debug messages Aver is a language for automatically verifying planners models and plan databases It allows the description of partial or complete plans and events that occur during planning that constitute expected behavior An assertion is a boolean statement that examines a particular aspect of a plan how ma
48. re given a command to deploy a particular instrument at a specific location the Rover needs to insure the following occurs in order The instrument must be first unstowed and then positioned Then if it decides not to perform another experiment with the same instrument it must stow the instrument 14 5 DEVELOPING YOUR OWN MODEL IN NDDL The model must be carefully crafted so that all component interactions are modeled so that correct command sequences can be inferred from this model In the next few sections we will show how to model each of the following model components locations and paths instruments batteries and rovers Then we ll show you how to connect all of these components and describe rules that govern the components and interactions Finally we ll create a small initial state that you ll be able to run with your new model 5 2 Locations and Paths When we model locations we re faced with a choice of modeling locations as an enumerated set and not representing the coordinates or to model locations as objects with coordinates as properties that are static with respect to time We will show both ways of modeling locations If we decided to choose to ignore properties of locations and instead enu merate all possible locations we would include the following in the model enum Location loci loc2 loc3 EUROPA 2 would interpret this as a new user defined type with values loc1 loc2 and loc3 Alternat
49. re is an active token with a predicate that matches a configuration rule in the model Unbound variables may occur in tokens objects or rules These must be bound to singletons before the planner can deem the plan complete There are a few caveats however EUROPA2 provides the ability to plan within a specific horizon Thus tokens and variables of tokens that lie outside of the horizon will not be deemed as flaws By default the horizon is INFINITY INFINITY but the horizon may be specified in the initial state Another caveat is that we provide a mechanism for specifying precisely the set of flaws that should be resolved before the planner finishes completing the partial plan This mechanism is explained in full in a paper 8 however we mention that flaws can be included in the set that need to be resolved via the specification of conditions that flaws must satisfy Thus a plan is not complete until all flaws that satisfy all conditions are resolved 3 6 Early vs Delayed Commitment EUROPA 2 provides at ways of controlling early vs delayed commitment through controlling variable assignments One example is how EUROPA 2 han dles temporal assignments EUROPA2 allows representation and reasoning over temporal intervals This flexibility turns out to be very useful when there s lack of knowledge on precisely when states will hold Temporal variable as signments can be delayed indefinitely by excluding them from the set of flaws This
50. rstanding of how EUROPA 2 works at the implementation level Finally we address the technical aspects of customization and extension De tailed reference material is included in the appendices 3 Concepts 3 1 Plans in Planning Scheduling and Execution Consider the scenarios illustrated in Figure 1 The first is an application of automated planning where the input planning problem is solved by a Planner 6 3 CONCEPTS Executive Commands Percepts Insertions amp Restrictions Plan Database Partial Restrictions Insertions amp Relaxtaions Deletions Restrictions Restrictions Planning gt amp Relaxtaions Restrictions amp Relaxtaions Partial C amp Relaxtaions Plan P Plan Partial Planning Database Plan Q Planning a Batch Planner b Mixed Initiative Planner c Plan based Executive with On Board Replanning Partial Plan Q Commands Plan Database Planner Figure 1 Sample Plan Database Applications to produce an acceptable partial plan The role of the Planner is to perform the search steps for resolving flaws T hus it interacts with a partial plan by imposing and retracting restrictions All operations are made on the Plan Database which stores the partial plan The second is an application of automated planning in concert with a User The User may introduce goals into a plan and change or undo decisions previously made by a Planner Additionally a User may employ a
51. rtial Plan represents a set of networks of states typically ordered by time though it can be ordered by precedence constraints or completely unordered 3 4 Token State Model 7 Inserted Inserted by by Execution External Client of a Compatibility activate merge Cam O cancel cancel Figure 2 Token State Transition Diagram e g a bag of states in planning scheduling and execution Each network is represented as an Object which corresponds to an instance of a model class Objects that impose mutual exclusions as well as a total order on its set of states is defined as a Timeline Objects that track numeric change are defined as Resources Objects that are just bags of states are called Objects EUROPA 2 provides means to specialize object implementations States in Objects are represented by Tokens and can correspond to activi ties in scheduling actions and fluents in planning and commands in execution Tokens are instances of predicates and like predicates they contain variables that can be used to augment state descriptions Some of these variables can be temporal variables indicating the temporal extent of the token state Rela tionships among tokens are defined by configuration rules Configuration rules specify relationships among tokens e g subgoaling relationships expressed as constraints between variables of tokens 3 4 Token State Model A token in EUROPA 2 evolves as decisions are made Initially a token may be
52. s unless needed for templates or proven performance Use STL classes and methods unless what you need is not provided Same goes for any other code Reuse as much as possible Pre processing Include system headers by using the angle bracket style include lt stdio gt Include user files by using the double quote style include File h Do not define your own pre processor macros to control level of or presence of debugging output or error checks Namespaces Use the std prefix or using namespace std when using STL Put Europa code in the Europa namespace Global Constants Use DEFINE GLOBAL CONSTANT and DECLARE GLOBAL CONSTANT for globals Static Class Members When handling static data you must provide an automatic purge mechanism or provide an explicit purge method 9 5 Appendix E Coding Guidelines 47 Module Initialization and Termination We should standardize method calls to initialization and termination methods Such as nddl initialization which cascades onto constraint engine initialization Iterator Use Use const iterators unless you have to use a non const iterator When using const iterators use iterator rather than iterator Pointer References Direct pointer references are discouraged use class Id instead When creating a reference create an m id member that holds the id that gets constructed in the constructor initializer
53. se the Con straint Engine provided with PLASMA to handle the more general classes of constraints and configure it to use the special purpose propagation algorithm you have to handle the types of constraints you already can handle In order to do this you must create a propagator wrapper on your propagation algorithm we ll explain how to do this in the next section You must then register this propagator with the Constraint Engine Then you must register the types of constraints with the Constraint Engine and the corresponding propagator This 42 8 CONTRIBUTING TO EUROPA 2 information will be captured by the ConstraintEngine who will route the con straint propagation request to the appropriate propagator All that you have to ensure is that the propagator is registered with the ConstraintEngine and that whenever you want to create a new constraint instance the type of constraint has been registered 7 4 Custom propagation How do we write custom propagation Currently EUROPA 2 provides a single way to configure custom propagation and that is through the use of propaga tors propagator is a core interface that provides the capability to manage an agenda of constraints A propagator provides query interfaces that provide sta tus enable execution allow registration of constraints and appropriate linkage to the Constraint Engine We currently provide a TemporalPropagator and a ResourcePropagator 7 5 Building model specializations H
54. struct an assembly with a PlanDatabase only or a PlanDatabase and a planner If your application doesn t require resource reasoning you don t have to include resources in your assembly There are a few examples in the code where we create specialized assemblies depending on the use we have An example is StandardAssembly which provides an example of an assembly that uses resource reasoning a plan database a constraint engine with a specialized STN temporal propagator and a chronological backtracking planner 7 1 Configuration and Assembly 39 specify canlgnore o Figure 15 Specify Collaboration Diagram When creating your assembly there are a few things you have to ensure happen in the right order These of course depend on the modules you ll be using ConstraintEngine 1 o nd Oo c RF win initialize type factories new Specialized TypeFactory initialize constraint factories REGISTER CONSTRAINTY create constraint engine create propagators purge all factories Object Token Constraint Rule Type call Entity purgeStarted delete constraint engine call Entity purgeEnded PlanDatabase e create schema e create constraint engine see above e create plan database e create temporal advisor if using a temporal network e create rules engine if using subgoaling 40 7 CUSTOMIZATION AND EXTENSION activate create instance specify Figure 16
55. tarts_before B A starts_before_end B A starts_during B Inverse relation A before B A any B A after B A contains B A contained by B A ends during B A starts during B A ends B A ends before B A starts_before_end B A ends after B A contains end B A equal B A met by B A meets DB A parallels B A paralleled_by B A starts B A starts_before B A starts_after B A ends after start B A contains start B The names used for the relations as defined in James Allen s original paper are Allen Relation A equals B A precedes B lt A follows B gt A meets B m A inverse meets B im A during B d A inverse during B id A starts B s A inverse starts B is A finishes B f A inverse finishes B if A overlaps B o A inverse overlaps B io Constraints A start B start A end B end A end lt B start A start gt B end A end B start A start B end A start gt B start A end B end A start B start A end gt B end A start B start A end B end A start B start A end gt B end A start gt B start A end B end A start B start A end B end A start B start A end gt B start A end lt B end A start B end A end gt B start A end gt B end Note the explicit naming of nearly all of the inverse relations The exceptions are equals its own inverse and precedes and follows which are each othe
56. ts to shoot images and shoot them either with a filter or without any filters Whether to use a filter or not is determined by the image request Let us first model a camera We can take advantage of the Instrument class and extend it with the properties we want cameras to have In NDDL we would write class Camera extends Instrument predicate ShootRequest bool filtering Location view int length j predicate PlaceFilter Location view 22 5 DEVELOPING YOUR OWN MODEL IN NDDL predicate Shoot Location view Notice that an image request requires that we specify whether or not to use a filter while shooting Furthermore each of the predicates keeps track of the location of the image that is to be taken We will need the navigator component to be at the location and remain at that location through the shoot The Location parameter of all predicates allows us ensure that we stay at the location through the entire shoot Here are the corresponding rules Camera ShootRequest eq length duration contained by Navigator At atc eq atc location view if filtering true Y meets object PlaceFilter s0 eq s0 view view if filtering false meets object Shoot s1 eq si view view Camera PlaceFilter eq duration 5 contained by Navigator At atc eq atc location view met by object ShootRequest s0 eq s0 view view meets object Shoot s1 eq s1 view view starts Battery
Download Pdf Manuals
Related Search