-
Notifications
You must be signed in to change notification settings - Fork 72
Example Rover
This tutorial will step you through a simple EUROPA application to provide you with a solid understanding of the capabilities of EUROPA and how to approach modeling application domains. We begin by introducing the goal before stepping through the stages of creating a EUROPA application for it.
Note that this example has much in common with the nddl snippets used on the NDDL Reference page. EUROPA includes working code for this example in this directory.
For many years NASA's Mars Exploratory Rover (MER) mission operated two rovers on the surface of Mars. The rovers moved between points of interest identified by scientists on earth to collect a range of scientific data by placing instruments and then transmitting the produced data back to earth. We are going to write the planning application for controlling a simplified version of these rovers.
To provide some context, the figure below shows NASA Ames' K9 rover that is used to experiment with advanced control concepts for future Mars rover missions. K9 is operating in a simulated Martian landscape (called Marscape) where it mirrors the MER mission. The first picture shows K9 in the context of its environments. The second picture shows K9 placing its sensor on a rock.
![k9Overview] (images/k9-rover-overview-photo.jpg)
Figure 1: K9 Rover at NASA Ames' Marscape while controlled by a EUROPA planner.
![k9SensorOnRock] (images/k9-sensor-on-rock-photo.jpg)
Figure 2: K9 Rover Placing a sensor at NASA Ames' Marscape.
We will build a batch application where we provide an application domain model and problem definition to the planner. The planner must then generate a plan to solve the problem. The figure below shows the main inputs and outputs to our application.
![simpleSample] (images/simple-sample-overview.jpg)
Figure 3: Application overview
Developing EUROPA applications is a design task that requires judgement and multiple iterations. We have found the steps in this tutorial useful in practice. The overall approach is to gradually build up a domain description adding detail methodically. This approach controls complexity by allowing the domain writer to focus only on well defined issues at a given instant.
The first stage is to draw a concept map of the entities in the application domain and their relationships. The figure below shows our concept map for the rover domain. We have identified locations and the paths between them as the key environment entities. The rover is the core vehicle, and includes possible commands scientists can issues, as well as subcomponents for the various things it can do. The navigator concept manages the location of the rover. The instrument concept will manage the instruments for sampling rocks. The battery concept is included to provide a place for managing the power used by the other components of the rover. The Lander corresponds to the vehicle used to deliver the rover to the planet surface and provides a communication service that the rover can use to transmit information to earth.
![rover concept] (images/RoverConcept.jpg)
Figure 4: Rover Application Concept Diagram
The next decision is to identify the entities in our concept map that will describe changes in state of the rover as it moves around its environment and performs experiments. We call each entity a timeline. The concept is best introduced by example. The rover in our domain is the actor we will be planning for and will contain all the timelines. Analyzing the components of the rover produces the following breakdown of timelines:
- Navigator controls the rover's movement between locations and holds position at a location.
- Rover manages instructions from the scientists tasking the rover.
- Instrument controls the API (commands) for the scientific instrument on the rover.
- !InstrumentLocation controls the location (or position) of the instrument on board the rover.
- !InstrumentState controls the state of the instrument.
The next stage is to identify the states that each timeline can be in. We call each state a predicate. The easiest way to identify the predicates is to think through the lifecycle of each timeline. The following figure shows the set of predicates we have identified on each timeline.
![rover timelines] (images/RoverTimelines.jpg)
Figure 5: Initial Timelines and Predicates
Working from the top of the figure downwards:
- Navigator: The rover is at a location or it going between locations.
- Rover: The activities the rover can perform are Go somewhere, !TakeSample, !PhoneHome or !PhoneLander.
- Instrument: The four commands that can be sent to the instrument are !TakeSample, Place, Stow, and Unstow.
- !InstrumentLocation: The instrument can be Stowed, Unstowed, or moving between those locations (Stowing or Unstowing).
- !InstrumentState: The instrument can be Free, Placed at a given location to take a sample, or in the process of Sampling.
As noted earlier, identifying the timelines and predicates is an iterative process. It would not be unusual to find new timelines while identifying predicates or to discover that two timelines could be collapsed into one. Please iterate and be comfortable with experimentation.
The next stage is to flesh out the properties of the predicates and the constraints between them. Using constraints among the predicates is the principal way to define acceptable behavior in the system (and disallow unacceptable behavior).
![takeSample] (images/RoverTakeSample.jpg)
Figure 6: Timelines and Predicates with Transitions between Predicates on each Timeline.
In the above figure, we show the constraints between the instrument !TakeSample command and other instrument timelines, using a variety of temporal relations. The 'contained by' constraint indicates the instrument must be in the unstowed location for the duration of the TakeSample (but could be unstowed before and after as well). The constraints with the !InstrumentState timeline show that when the !TakeSample starts, a Placed state must end ('met by'), and a Sampling state must begin; the use of 'equals' for the Sampling state indicates that it will begin and end at the same times as the !TakeSample.
Our encoding of the Rover domain is available here. We will step through each of the model files and explain how it was derived form our analysis above and the NDDL constructs that were used. Rover-model.nddl contains the application domain model and Rover-inital-state.nddl contains a sample problem definition.
We begin with the application domain model.
The concept of locations is encoded in the Location class. The class has three attributes. The name is a symbolic name for the location. The x and y attributes are coordinates. We have decided to position all our locations on a Euclidean Plane. The second part of the class specifies the constructor. The constructor defines how the attributes of a location are initialized when a new instance is created. We simply provide a signature that allows us to create locations with the name and coordinates specified; the constructor's job is to copy those initial values into the correct member variables.
class Location {
string name;
int x;
int y;
Location(string _name, int _x, int _y){
name = _name;
x = _x;
y = _y;
}
The Path class connects pairs of locations and its implementation follows a similar pattern to the Location class. Paths have a symbolic name and a pair of locations that they connect. The cost parameter will be used to compute the amount of battery power that will be consumed while traversing a path. The constructor's role is again just to take initial values for each of a path's attributes.
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;
}
}
We next encode the Battery that will be used to power the rover. EUROPA provides a Reservoir class for modeling consumable resources like batteries and fuel cells that have a numeric capacity that is produced and consumed during a plan. The Battery class specializes the general Reservoir class. It takes three arguments: an initial capacity ic, a minimum charge level ll_min and a maximum charge level ll_max. The Battery constructor delegates the creation of an instance to its parent or super class, the general Reservoir class. The profieType string is used to indicate to the EUROPA solver what type of algorithms to use for calculating resource flaws and inconsistencies more details.
class Battery extends Reservoir
{
string profileType;
Battery(float ic, float ll_min, float ll_max)
{
super(ic, ll_min, ll_max);
profileType="IncrementalFlowProfile";
}
}
}
We now move on to encode the components of the rover. We begin with the rover's navigator. This class contains the two predicates we identified earlier. The At predicate models the concept of the rover being at a particular location. The Going predicate models the concept of moving between locations. The neq construct is a constraint that ensures the rover does not attempt to traverse a path that start and finishes in the same location.
class Navigator extends Timeline
{
predicate At { Location location; }
// Rover may be going between two locations.
predicate Going{
Path path;
Location from;
Location to;
neq(from, to); // prevents rover from going from a location straight back to that location.
}
}
Before we get to the Instrument timeline itself, we consider two sub-timelines that it will use. !The InstrumentLocation timelines maintains. These predicates are declared but have no accompanying logic (in effect, the only constraint is that they occur on a single timeline, so cannot overlap).
class InstrumentLocation extends Timeline
{
predicate Stowed{}
predicate Stowing{}
predicate Unstowed{}
predicate Unstowing{}
}
Similarly, we create a timeline for the state of the instrument, where the Placed and Sampling predicates include the specific location.
class InstrumentState extends Timeline
{
predicate Placed {Location rock;}
predicate Sampling {Location rock;}
predicate Free {}
}
Finally, the Instrument timline itself details the management of the rover's instrument for taking samples and for keeping the instrument safely stowed while moving. It contains !InstrumentLocation and !InstrumentState objects (timelines). Notice that the !TakeSample and Place actions each include a Location parameter, and that each action has a specfied duration (for example, Place takes 3 time units).
class Instrument
{
Rover rover;
InstrumentLocation location;
InstrumentState state;
Instrument(Rover r)
{
rover = r;
location = new InstrumentLocation();
state = new InstrumentState();
}
action TakeSample{
Location rock;
eq(10, duration); // duration of TakeSample is 10 time units
}
action Place{
Location rock;
eq(3, duration); // duration of Place is 3 time units
}
action Stow{
eq(2, duration); // duration of Stow is 2 time units
}
action Unstow{
eq(2, duration); // duration of Unstow is 2 time units
}
}
With the predicates defined we now move on to specify the detailed constraints on each beginning with !TakeSample. These constraints ensure that the state switches from Placed to sampling when the sampling starts, that the location of the instrument is Unstowed and that the rock being sampled matches the rock variables for the !InstrumentState.Sampling variable. The predicate consumes 120 units of battery power.
Instrument::TakeSample
{
met_by(condition object.state.Placed on);
eq(on.rock, rock);
contained_by(condition object.location.Unstowed);
equals(effect object.state.Sampling sample);
eq(sample.rock, rock);
starts(effect object.rover.mainBattery.consume tx);
eq(tx.quantity, 120); // consume battery power
}
The Place predicate is similar to the !TakeSample predicate.
Instrument::Place
{
contained_by(condition object.location.Unstowed);
meets(effect object.state.Placed on);
eq(on.rock,rock);
starts(effect object.rover.mainBattery.consume tx);
eq(tx.quantity, 20); // consume battery power
}
Unstow has three conditions on the InstrumentLocation timeline; it is preceded by a Stowed predicate, matches an Unstowing predicate and is followed by an Unstowed predicate. It also consumes some battery charge.
Instrument::Unstow
{
met_by(condition object.location.Stowed);
equals(effect object.location.Unstowing);
meets(effect object.location.Unstowed);
starts(effect object.rover.mainBattery.consume tx);
eq(tx.quantity, 20); // consume battery power
}
The Stow predicate is the same idea.
Instrument::Stow
{
met_by(condition object.location.Unstowed);
equals(effect object.location.Stowing);
meets(effect object.location.Stowed);
starts(effect object.rover.mainBattery.consume tx);
eq(tx.quantity, 20); // consume battery power
}
}
The Rover class pulls together all the components we have defined so far and manages instructions from the scientist user to move (Go), take samples (!TakeSample), or transmit information back to the lander (!PhoneLander) or earth (!PhoneEarth). It has an attribute for the navigator, instrument, and battery classes. The constructor takes an instance of the Battery class and creates instances of the other classes to setup the rover.
class Rover
{
Navigator navigator; // Keeps track of Rover's position
Instrument instrument; // Keeps track of Instrument's state
Battery mainBattery; // Provides power
Rover(Battery b)
{
navigator = new Navigator();
instrument = new Instrument(this);
mainBattery = b;
}
action Go { Location dest; }
action TakeSample { Location rock; }
action PhoneHome{} // Communicate material back to earth
action PhoneLander{} // Communicate material back to lander
}
The definitions of the Rover actions will be familiar from previous predicates. The Go predicate specifies that the instrument must be stowed, defines what the Navigator timeline should look like before during and after the Go, and matches the destination with the Path 'from' variable. Finally, the Go action consumes battery charge.
Rover::Go
{
// Instrument must be stowed while driving
contained_by(condition object.instrument.location.Stowed);
met_by(condition object.navigator.At _from);
meets(effect object.navigator.At _to);
eq(_to.location, dest);
// Find a path
Path path;
// The path used must be between the 2 points
eq(path.from, _from.location);
eq(path.to, dest);
equals(effect object.navigator.Going going);
eq(going.path,path);
eq(going.from,_from.location);
eq(going.to,dest);
// Pull power from the battery equal to the path cost.
starts(effect object.mainBattery.consume tx);
eq(tx.quantity, path.cost);
}
Consider !TakeSample next. The contained_by constraint ensures that the Rover stay at one location throughout the sampling. The equals constraint ensures that the instrument does indeed take the sample, and that it is taking a sample from the correct rock. The condition allows the predicate to either meet a !PhoneHome or !PhoneLander predicate to transmit the results of the sampling back to earth. Either way can be used by the planner unless we set specify the value of the OR variable.
Rover::TakeSample
{
// Rover must be at the target rock throughout
contained_by(condition object.navigator.At at);
eq(at.location, rock);
equals(object.instrument.TakeSample ts);
eq(ts.rock, rock);
// Make contact with results. Prefer to phone home, but
// also allow contact to lander instead as a relay
bool OR;
if (OR == false) {
meets(object.PhoneHome t0);
}
if (OR == true) {
meets(object.PhoneLander t1);
}
}
The !PhoneHome and !PhoneLander predicates are specified next. Both use battery power. !PhoneHome is more expensive as the signal needs to be transmitted back to earth requiring much more power.
Rover::PhoneHome
{
starts(object.mainBattery.consume tx);
eq(tx.quantity, 300); // consume battery power
}
Rover::PhoneLander
{
starts(object.mainBattery.consume tx);
eq(tx.quantity, 20); // consume battery power
}
We have now completed the NDDL modeling we need to describe our application domain and it is now possible to describe problems that we want our planner to solve.
The initial state file contains an example planning problem with a specific set of locations and paths. The first line of the file just includes the domain model file we detailed in the previous section.
#include "Rover-model.nddl"
The environment is configured to have five locations - four rocks and a single lander.
Location lander = new Location("LANDER", 0, 0);
Location rock1 = new Location("ROCK1", 9, 9);
Location rock2 = new Location("ROCK2", 1, 6);
Location rock3 = new Location("ROCK3", 4, 8);
Location rock4 = new Location("ROCK4", 3, 9);
We define three paths that lead from the lander to the location named rock4. The paths vary considerably in the amount of battery energy needed to traverse them.
Path p2 = new Path("Very Long Way", lander, rock4, 2000.0);
Path p3 = new Path("Moderately Long Way", lander, rock4, 1500.0);
Path p1 = new Path("Short Cut", lander, rock4, 400.0);
We define a single battery with an initial and maximum capacity of 1000 units. The battery may be drained as low as 0 units.
Battery battery = new Battery(1000.0, 0.0, 1000.0);
We define a single rover, spirit, and pass it the battery we just defined.
Rover spirit = new Rover(battery);
We have now defined all the objects in our domain and we can close the database and begin specifying the state of the world.
close();
We define the initial state by creating an At token called initialPosition. It is constrained to start at the same time the planning horizon starts and the location attribute is set to being the lander. The result is to place the rover at the lander at time zero.
fact(spirit.navigator.At initialPosition);
eq(initialPosition.start, 0); // What time - the start of this planning horizon
eq(initialPosition.location, lander); // What position - the lander
We define the instrument to start in the Stowed location and the _Free state.
fact(spirit.instrument.location.Stowed stowed);
eq(stowed.start, 0);
fact(spirit.instrument.state.Free free);
eq(free.start, 0);
We define the goal as taking a sample of rock4 starting at time 50.
goal(spirit.TakeSample sample);
sample.start.specify(50);
sample.rock.specify(rock4); // Want to get to rock4
With the model and the initial state now specified it is time to start planning.
Run the example:
% cd $EUROPA_HOME/examples/Rover
% ant
Click on "Go" in the solver dialog, then run "setupDesktop();" from the !BeanShell console. You will see the resulting schedule for this particular example (windows have been rearranged in this screenshot to show everything):
![rover results] (images/Rover.results3.png)
Figure 7: EUROPA UI Showing a Rover domain solution
A couple of observations:
- The red and blue curves bound the possible batter charge. The difference between the two is due to flexibility in the plan regarding when the navigation and sampling take place. The red curve shows the charge when they occur as soon as possible, and the blue curve shows them if everything is delayed as long as possible.
- The bottom window displays a gantt chart for the Rover, Navigator and Instrument timelines in this problem. Hover the mouse over any piece (green rectangle) of the gantt chart to see details displayed in the Details window. In this screenshot, the mouse was hovered over the large box on the Navigator timeline, which is an 'At' predicate.