7.2.1 Problem Domains

The domain involves a team of rovers that must resolve conflicts over shared resources. We generate two classes of maps within which the rovers move. For one, we randomly generate a map of triangulated waypoints (Figure 27). For the other, we generate corridor paths from a circle of locations with three paths from the center to points on the circle to represent narrow paths around obstacles (Figure 28). This ``corridor'' map is used to evaluate the CFTF heuristic. We then select a subset of the points as science locations (where the rovers study rocks/soil) and use a simple multiple traveling salesman algorithm to assign routes for the rovers to traverse and perform experiments. The idea is that a map of the area around a lander is constructed from an image taken upon landing on Mars.

Figure 27: Randomly generated rectangular field of triangulated waypoints

Figure 28: Randomly generated waypoints along corridors

Paths between waypoints are assigned random capacities such that either one, two, or three rovers can traverse a path simultaneously. Only one rover can be at any waypoint, and rovers may not traverse paths in opposite directions at the same time. These constraints are modeled as metric resources. State variables are also used to ensure rovers are at locations from which they are about to leave. In addition, rovers must communicate with the lander for telemetry using a shared channel of fixed bandwidth (metric resource). Depending on the terrain between waypoints, the required bandwidth varies. 80 problems were generated for two to five rovers, three to six science locations per rover, and 9 to 105 waypoints. In general, problems that contain fewer waypoints and more science goals are more difficult because there are more interactions among the rovers.

Schedules consist of an abstract task for each rover that have an $and$ decomposition into tasks for visiting each assigned science location. Those tasks have an $or$ decomposition into the three shortest paths through the waypoints to the target science location. The paths have an $and$ decomposition into movements between waypoints. Additional levels of hierarchy were introduced for longer paths in order to keep the offline resource summarization tractable. Schedules ranged from 180 to 1300 tasks.