IEEE Robotics & Automation Magazine - March 2015 - 68

Perception

Mission
Goals

Task Allocation

Reference
Path

Motion Planning

T, S

Spatial
Constraints

Coordination

Collision Prediction

T, S
Obstacle
Poses and
Bounding
Boxes
Temporal
Constraints

T, S

Spatial and
Temporal
Constraints

Control
Control
T, S Actions

Temporal
Constraints

Sensor
Readings

Constraint-Based Representation (Trajectory Envelopes f)

Figure 3. The SAUNA functional schema. The dashed arrows indicate information extracted by each module from the constraint-based
representation, which can be either temporal envelopes (T ) or spatial envelopes (S). The continuous arrows indicate the refinements
that modules post to the overall problem, i.e., temporal and/or spatial constraints that modify the envelopes. The dotted arrows indicate the
inputs and signals exchanged between modules.

particular set of constraints. In SAUNA, we have divided this
collection of reasoning capabilities into six functional modules, as shown in Figure 3.
● Perception is responsible for constructing collections of
spatial constraints, which subsume vehicles' paths, given
the perceived drivable area. In addition, perception is
responsible for localization and fixed/mobile obstacle
tracking. Note that perception dynamically posts spatial
constraints, as obstacles may become known gradually
over time.
● Task allocation addresses mission goals and computes startto-destination pairs of regions that vehicles should visit
(given the perceived drivable area). It also posts temporal
constraints stating the desired deadlines or release times
(i.e., when vehicles should be in the designated areas).
● Motion planning uses the perceived drivable area to compute sets of spatial constraints, sequenced by temporal constraints, which identify how vehicles should displace themselves across the drivable area to achieve the constraints
posted by task allocation. These sequences are trajectory
envelopes containing paths that are guaranteed to be kinematically feasible.
● Coordination is responsible for further refining the trajectory envelopes with constraints that exclude deadlocks and
collisions between controlled vehicles. The input, calculated by motion planning, is a sequence of overlapping
convex polyhedra for each robot. The output consists of
temporal constraints that exclude trajectories leading to
vehicles being in overlapping areas during overlapping
temporal intervals as well as temporal profiles that exceed
the known speed limits for vehicles.
● Collision prediction imposes constraints that exclude collisions with vehicles that are not autonomously guided and
other dynamic obstacles in the environment. It enriches the
trajectory envelopes with spatial and temporal constraints,
which guarantee the absence of collisions, given current
68

IEEE ROBOTICS & AUTOMATION MAGAZINE

march 2015

perception, known trajectory envelopes for controlled vehicles, and the predicted behavior of dynamic obstacles.
● Control modules on board the vehicles are responsible for
computing control actions for vehicles in such a way that all
spatial and temporal constraints (which have been refined
by the previous modules) are enforced. In addition, controllers measure the performance they achieve in following a
reference trajectory. This allows them to dynamically impose further constraints that restrict the trajectories of all
vehicles in the fleet to maximize the collective performance.
As shown in Figure 3, all modules reason upon the current
collection of spatial and temporal constraints (S and T,
respectively) in the common constraint-based representation.
They post specific constraints-spatial, temporal, or both-to
the common constraint-based representation to refine the trajectory envelopes because of their particular inference procedures. The modules refine the representation continuously and
are triggered by their inputs. Perception may refine the spatial
envelopes when sensors detect changes in the environment;
task planning is activated when mission goals appear or
change, or when the temporal or spatial envelopes of existing
trajectories are modified; motion planning recomputes polyhedra sequencing when new goals appear and/or when spatial
constraints change; coordination is triggered when trajectory
envelopes overlap both spatially and temporally, a condition
that can exist when envelopes are first computed or when temporal constraints are added by collision prediction; the temporal and spatial envelopes, as well as newly perceived moving
objects, trigger collision prediction; and control modules on
board the vehicles adapt control actions in the face of new trajectories to follow. The overall result is a constraint network
that represents a feasible set of trajectory envelopes for all vehicles in the fleet.
In the remainder of this article, we provide a brief overview of each module and present an instance of the entire system. The description also focuses on which of the

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - March 2015