vey goal, where surveys follow a waypoint sequence.
The remaining uncertainty in an area survey is the
length of the search pattern that has yet to be traversed by an assigned vehicle.
Figure 13 shows the plots of the four Goal Lifecycle
strategies. Graph 13a depicts that each survey goal is
formulated by generating constraints on the maxi-
mum allowable uncertainty over time. GRIM selects
a single goal (the airport survey goal) to pursue and
expands it (that is, generates plans to achieve it).
These plans’ expectations (depicted as a change in
the uncertainty over time) are shown in graph 13b.
GRIM commits to a single expansion and dispatches
it to the vehicles. Graph 13c depicts the correspon-
ding expectations and performance bounds that are
generated by the dispatch strategy. Graph 13d dis-
plays execution performance over time, as obtained
by the monitor strategy. During execution, when the
vehicle’s performance is predicted to violate a goal
constraint (for example, in graph 13d, when its exe-
cution reaches the worst-case time bound), GRIM
triggers the evaluate strategy to determine what vio-
lation occurred. If the execution satisfies the com-
pletion criteria, the goal is marked as completed and
dropped. If it instead violates the goal’s constraints,
it is marked as failed and dropped. Otherwise, if the
performance violates the execution bounds, a resolve
strategy is activated to adjust the goal (for example,
its expansion) before continuing execution. The
selected resolve strategy can transition the goal back
to an earlier Goal Lifecycle mode (see figure 3) (for
example, it may repair the committed expansion by
adjusting parameters that affect the expectations and
bounds). Alternately, a resolve strategy may force
GRIM to expand the goal again and then commit to
and dispatch one of the new expansions.
We conducted an ablation study with GRIM’s
resolve strategies (Johnson et al. 2016) on simulated
FDR scenarios. We found that they allow GRIM to
perform GR during execution, that they improve its
performance, and that they enable it to successfully
complete more goals under uncertain and changing
conditions. By associating the Goal Lifecycle strategies with a single measure, GRIM can define clear
decision points that increase the transparency of its
decision process. For an agent that can change its
goals and plans, transparency in how those decisions
are made is critical for promoting operator trust.
GRIM automatically synthesize FSAs whose execution by individual vehicles is guaranteed to satisfy
their LTL specification. Balch et al. (2006) also use
FSAs for mobile robot guidance. Hand-coding an FSA
for each execution of a robot is tedious and error
prone. Kress-Gazit, Fainekos, and Pappas (2009)
instead synthesize an FSA from an LTL specification
using a game-theoretic approach in which the robot
acts to achieve its goals versus actions taken by an
adversary. This strategy guarantees correct behavior if
the LTL specification is never violated, but synthesis
is quadratic in the number of goals (Bloem et al.
2012) and is thus intractable for large robot teams.
GRIM instead preselects missions for vehicles prior to
FSA synthesis, which reduces the size of the LTL specification and the computation time required for synthesis.
Goal Lifecycle strategies are themselves important
research topics, and each can be accomplished using
a variety of algorithms. For example, the goal selection method can vary widely, from domain-specific
rule-based selection (Thangarajah et al. 2010) to the
evaluation of domain-independent heuristics (
Wilson, Molineaux, and Aha 2013), or goal priorities
(Young and Hawes 2012). Many planning algorithms
can be used for goal expansion, including the sophisticated hierarchical (Shivashankar, Alford, and Aha
2017) and temporal planners (To et al. 2017) that our
group developed and plan to integrate with future
GR agents. Finally, in many cases the planner can
generate plan execution expectations, but in some
situations additional simulations and deliberation
may be required (Auslander et al. 2015).
Future extensions of GRIM will investigate additional goal types (for example, a communications
Figure 12. Scenario for Testing GRIM’s Ability to Control Two Vehicles
in a Simulated Foreign Disaster Relief Operation.
The vehicles’ goals include completing a survey of the airport and office
buildings, and establishing a communications relay for any VIPs found.