NASA/TM–2012–216032

Optimal routing and control of

multiple agents moving in a

transportation network and

subject to an arrival schedule and

separation constraints

A. V. Sadovsky

Ames Research Center, Moffett Field, California

D. Davis

UCLA, Department of Mathematics, Los Angeles, CA 90095-1555

D. R. Isaacson

Ames Research Center, Moffett Field, California

July 2012
NASA STI Program . . . in Profile

Since its founding, NASA has been

dedicated to the advancement of

aeronautics and space science. The

NASA scientific and technical

information (STI) program plays a key

part in helping NASA maintain this

important role.

The NASA STI Program operates

under the auspices of the Agency Chief

Information Officer. It collects,

organizes, provides for archiving, and

disseminates NASA’s STI. The NASA

STI Program provides access to the

NASA Aeronautics and Space

Database and its public interface, the

NASA Technical Report Server, thus

providing one of the largest collection

of aeronautical and space science STI

in the world. Results are published in

both non-NASA channels and by

NASA in the NASA STI Report Series,

which includes the following report

types:

• TECHNICAL PUBLICATION.

Reports of completed research or a

major significant phase of research

that present the results of NASA

programs and include extensive data

or theoretical analysis. Includes

compilations of significant scientific

and technical data and information

deemed to be of continuing reference

value. NASA counterpart of

peer-reviewed formal professional

papers, but having less stringent

limitations on manuscript length and

extent of graphic presentations.

• TECHNICAL MEMORANDUM.

Scientific and technical findings that

are preliminary or of specialized

interest, e.g., quick release reports,

working papers, and bibliographies

that contain minimal annotation.

Does not contain extensive analysis.

• CONTRACTOR REPORT.

Scientific and technical findings by

NASA-sponsored contractors and

grantees.

• CONFERENCE PUBLICATION.

Collected papers from scientific and

technical conferences, symposia,

seminars, or other meetings

sponsored or co-sponsored by NASA.

• SPECIAL PUBLICATION.

Scientific, technical, or historical

information from NASA programs,

projects, and missions, often

concerned with subjects having

substantial public interest.

• TECHNICAL TRANSLATION.

English- language translations of

foreign scientific and technical

material pertinent to NASA’s

mission.

Specialized services also include

creating custom thesauri, building

customized databases, and organizing

and publishing research results.

For more information about the NASA

STI Program, see the following:

• Access the NASA STI program home

page at http://www.sti.nasa.gov

• E-mail your question via the Internet

to help@sti.nasa.gov

• Fax your question to the NASA STI

Help Desk at 443-757-5803

• Phone the NASA STI Help Desk at

443-757-5802

• Write to:

NASA STI Help Desk

NASA Center for AeroSpace

Information

7115 Standard Drive

Hanover, MD 21076–1320
NASA/TM–2012–216032

Optimal routing and control of

multiple agents moving in a

transportation network and

subject to an arrival schedule and

separation constraints

A. V. Sadovsky

Ames Research Center, Moffett Field, California

D. Davis

UCLA, Department of Mathematics, Los Angeles, CA 90095-1555

D. R. Isaacson

Ames Research Center, Moffett Field, California

National Aeronautics and

Space Administration

Ames Research Center

Moffett Field, California 94035-0001

July 2012
Acknowledgments

D. Davis’s research was supported by NSF Grant DGE-0707424.

The use of trademarks or names of manufacturers in this report is for accurate reporting and

does not constitute an offical endorsement, either expressed or implied, of such products or

manufacturers by the National Aeronautics and Space Administration.

Available from:

NASA Center for AeroSpace Information

7115 Standard Drive

Hanover, MD 21076-1320

443-757-5802
Abstract

We address the problem of navigating a set of moving agents, e.g. automated guided vehicles, through a transportation network so as to bring

each agent to its destination at a specified time. Each pair of agents is required to be separated by a minimal distance, generally agent-dependent,

at all times. The speed range, initial position, required destination, and

required time of arrival at destination for each agent are assumed provided. The movement of each agent is governed by a controlled differential equation (state equation). The problem consists in choosing for

each agent a path and a control strategy so as to meet the constraints

and reach the destination at the required time. This problem arises in

various fields of transportation, including Air Traffic Management and

train coordination, and in robotics. The main contribution of the paper

is a model that allows to recast this problem as a decoupled collection of

problems in classical optimal control and is easily generalized to the case

when inertia cannot be neglected. Some qualitative insight into solution

behavior is obtained using the Pontryagin Maximum Principle. Sample numerical solutions are computed using a numerical optimal control

solver.

1 Introduction

Problems in coordinated motion planning for multiple agents can be

roughly classified into two disjoint categories, decoupled coordination

(each agent’s motion is planned separately, then the plans are reconciled),

and centralized coordination (all the agents’ motions are planned simultaneously, with the interaction constraints considered from the start) [1].

The problems considered in this paper fall in the latter category. Centralized coordination of multiple agent motion has been approached using various types of mathematical models, discrete (see, for example, [2]

and references therein) and continuous (see, for example, [1, 3–5], and

references therein). A review of research on multi-robot coordination

problems can be found in [1, section 1.1].

In a number of coordination problems, the moving agents are confined

to a transportation network (also known as roadmap coordination space

[1]). A general mathematical model of a transportation network is a

multigraph [6] with the vertices being points in a Euclidean space and

edges being parametrized curves connecting pairs of vertices. Examples

of such networks include railroad networks for trains, railroad networks

for industrial robots, trolley and tram car networks, and airspaces with

fixed nominal routes.

A subclass of network-confined coordination problems consists of

those where the agents’ paths are not given but sought as part of solving the problem. In such problems, the system exhibits behaviors both

1
continuous (the agent’s motion along an edge) and discrete (an agent’s

choice between two edges emanating from the same vertex). This coupling of the two behaviors suggests hybrid control systems (HCS) [7] as

a suitable class of models for approaching the problem. Hybrid systems

have been applied to various problems of transportation (e.g., highway

traffic [8,9]), and in particular to aerospace problems [10–12], and are applied here to the problem of finding routes and speed advisories for a set

of agents moving in a transportation network with separation constraints

and an arrival schedule imposed. Namely, one is given the following data:

1. A directed multigraph G = (V, E), each vertex v ∈ V being a

point in a Euclidean space E of dimension 2 or 3. If e ∈ E is an

edge from vertex v1 to vertex v2, then the nominal route segment

from waypoint v1 to waypoint v2 is a curve in E, connecting v1 to

v2. All such curves will henceforth be assumed rectifiable [13] and

capable of a parameterization which is continuous and piecewise

continuously differentiable. A cusp in the curve can be traversed

with the assumption (made throughout this paper, but capable of

relaxation) that inertia is neglected, and approximately smoothed

if inertia is to be taken into account. A graph-theoretic path [6]

in G is, therefore, associated (and, henceforth, identified) with a

spatial path that can be traversed by a moving agent. A vertex of

G of indegree ≥ 2 [6] (respectively, outdegree ≥ 2) corresponds to

two or more route segments merging (respectively, diverging). The

modeling framework below imposes no restrictions on the outdegree

or indegree of a vertex.

2. A finite set

A = {1, . . . , A} (1)

of moving agents α ∈ A in G. If agent α is moving along a path

in G, the agent’s position is specified by the arc length coordinate

x

α along the path.

3. For each agent α ∈ A, a specification of the agent’s initial position x

INIT;α, required destination xDEST;α, and the required time

t

DEST;α of arriving at the destination. Here xINIT;α and xDEST;α

are points in G, each point specified, for example, by an edge in G

and a fractional distance along that edge.

4. The inertia-free state equations [14] (henceforth the dot denotes

differentiation with respect to physical time t)

x ̇

α = sα

, α ∈ A,

where the s

α’s are the corresponding speeds, describing the motion

of those agents α that have not yet reached their destination. In

what follows, and with the details provided below, the coordinates

2
x

α will play the role of state variables; the speeds sα, of the control

variables.

5. State constraints: the separation requirement for each pair of agents.

This requirement is described mathematically, in terms of the coordinates x

α, in section 3.

6. Control constraints: bounds on the speeds s

α

e

.

7. A cost functional, specified below.

The problem, defined in detail below (definition 4.1) as the Scheduled

Routing Problem, consists in finding for each agent α ∈ A a path p(α) in

G from x

INIT;α to xDEST;α and a control strategy sα

p(α)

(t) (i.e., a function

from the time domain of the model to the set of admissible controls)

such that the resulting movements x

α(t) along the corresponding paths

constitute a state trajectory that satisfies the above state and control

constraints and that minimizes the cost.

In this paper, we use an HCS framework to formulate a model specialized to the above problem. The main contributions of this model are

as follows:

• Reduction of the problem to a special case of an HCS where each

solution trajectory lies in only one control mode.

• A clear application of Depth-First Search [15] to search through

the control modes as economically as possible given the possibly

exponential size of the problem. (In the worst case when every

agent can be assigned to any of the paths, and when each edge can

serve as a path by itself, the number of agent-to-path assignments,

i.e. of functions μ : A → E, is |E|

|A|. This upper bound, however,

is a crude overestimate. Better ones are discussed below.)

• Reduction of each control mode to a problem in classical deterministic optimal control, which allows, at least in principle, application

of the fundamental results of Pontryagin [16] and Bellman [17], and

of the numerical algorithms that have been developed and implemented [18–20].

• A natural way to capture an agent’s exiting the system; see Remark

4.1, below.

These contributions together allow for parallel computation of solutions:

the classical optimal control problems corresponding to different control

modes can be solved in parallel, and their obtained minimal costs values

compared. Furthermore, the Depth-First Search algorithm itself admits

a parallel implementation [21].

The new hybrid model is formulated in section 2. The classical deterministic optimal control corresponding to a given control mode is

3
formulated in section 4. Numerical solutions to some instances of the

problem are given in section 5.

2 An HCS formulation

The HCS defined in this section will be instrumental in a precise formulation of the Scheduled Routing Problem. Assume the data 1)-7), listed

in the third paragraph of section 1.

• For each agent α ∈ A, let e

INIT;α denote the edge occupied initially

by agent α. (Two or more agents can occupy the same edge.)

• Let P



e

INIT;α, eDEST;α



be the set of all paths in the multigraph

that begin with the edge e

INIT;α and end with the edge eDEST;α

that contains x

DEST;α. The length of a path p ∈ P 

e

INIT;α, eDEST;α



will be denoted l(p).

• Define a control mode μ as a mapping that assigns each agent α to a

path in P



e

INIT;α, eDEST;α



. In more detail, μ is a mapping from

the set A of moving agents to the union ∪αP



e

INIT;α, eDEST;α



such that

μ(α) ∈ P e

INIT;α

, eDEST;α



for each α ∈ A

• For agent α, each path μ(α) ∈ P e

INIT;α, eDEST;α



is parameterized by arc length. For computational convenience, the arc length

coordinate increases along the path, with the destination coordinate x

DEST;α being zero for each α. Thus, xα

μ ∈ [−l(μ(α)), 0],

and

x

DEST;α = 0

This convention ensures that an agent’s destination is a vertex in

the transportation network and, furthermore, that it is the same

vertex in all control modes.

• Each agent α in each control mode μ is required to reach its destination x

α

μ = x

DEST;α = 0 at a prescribed time tDEST;α. Upon

reaching destination, the agent is no longer in the model; this is

reflected in the restriction on the time domains of the individual

equations in the dynamical law (2), stated below.

• In each μ, have the arc length coordinate x

α

μ

evolve according to

the dynamical law

y ̇

α

μ

(t) = s

α

μ

(t) for 0 ≤ t ≤ t

DEST;α

, α ∈ A, (2)

4
where s

α

μ

is the control variable corresponding to the agent’s speed

of motion along the path. In this formulation, the equations that

constitute the dynamical law are imposed over different (albeit

overlapping) time domains. The problem, however, will be converted below to one where all dynamical law equations are imposed

over the same (rescaled) time domain.

• For each μ and each α, impose the arrival requirement

x

α

μ



t

DEST;α



= x

DEST;α

(3)

• For each μ and each α, impose the speed ranges

s

MIN;α

μ ≤ s

α

μ ≤ s

MAX;α

μ

(4)

3 The geometry of separation constraints

In some transportation types, including aircraft and trains, every pair of

moving agents must be be separated by a distance no smaller than a predetermined minimal separation. For example, the minimal separation

requirements for air traffic in the U.S. are defined in [22] and depend on

numerous factors, including airspace type, air traffic automation systems

in use, and aircraft weight classes (the classes defined in [22] are: Small,

Large, Heavy, B757). Other types of moving agents, e.g. industrial

robots, may also be subject to complicated, asymmetric, and anisotropic

(e.g., for aircraft, altitude-dependent) separation requirements. The separation requirement will be a key constraint on the state variables in the

Scheduled Routing Problem formulated in section 4.2.

2

1

e1

e2

a1

a2

0

θ

2

1

e1

e2

c1a1

c2a2

0

θ

(a) (b)

Figure 1. Agents 1, 2 on their respective rectilinear edges e1, e2, which

share a common vertex, taken as the origin 0 in R2. The orientation

of the edges is not specified. (a) The unit vectors a1, a2 are collinear

with the respective edges, but their directions do not necessary agree

with the edges’ orientations. (b) With suitably chosen scalar coefficients

c1, c2, the vectors c1a1 and c2a2 are the respective position vectors of the

two agents.

5
No attempt is made in this paper to capture all such requirements in

detail (see, however, section 6.3) for a discussion of anisotropy in separation requirements arising from altitude dependence). Instead, we will

use conservative approximations, addressing only the following asymmetry: if two moving agents are in-trail (i.e., one is directly following

the other along a route segment which is not necessarily in a horizontal

plane), then the minimal separation can depend on the weight class of

the leading and trailing agent. To capture this potential asymmetry,

for each pair α1, α2 of agents with the first one leading, we introduce

the minimal separation rα1,α2. If the asymmetry takes place, it can be

written

rα1,α26= rα2,α1(5)

We now calculate the set of all states, in a control mode μ of a hybrid

system described above, where at least two agents violate the separation

requirement. The scenario shown in Figure 1A has two agents on two

different rectilinear edges, which need not lie in a horizontal plane, with a

common vertex and no specified orientation. (If the edges are curvilinear

with low curvature near a common vertex or intersection, these portions

can be approximated by linear segments; otherwise, the analysis becomes

considerably more complicated.)

Remark 3.1. Since edge orientation is not specified, Figure 1 describes

four cases: one where both agents are moving toward the common vertex,

one where both agents are moving away from the common vertex, and

two more cases in which one agent is moving toward, and the other away

from, the common vertex.

c2

c1

Figure 2. An example of two elliptical sectors in the c1c2-plane corresponding to conflicting states.

The asymmetry of the gray-shaded region about the dashed diagonal

is the asymmetry (5).

We will use the Euclidean inner product h·, ·i and the corresponding

norm || · || in the 2-D space containing the two edges. Pick the common

vertex as the origin and the unit vectors a1, a2 as the basis vectors that,

regardless of the edge orientations, point from the origin toward the

6
respective agents. With suitable scalars c1, c2, the vectors c1a1 and c2a2

are the agents’ respective position vectors. The squared distance between

the two agents is

||c1a1 − c2a2||2 = (c1)

2 + (c2)2 − 2c1c2ha1, a2i (6)

Equating the latter expression to the squared minimal separation, say,

r

2

1,2

, we obtain the equation

(c1)

2 + (c2)2 − 2c1c2ha1, a2i = r2

1,2

(7)

of an ellipse in the c1c2-plane. The corresponding set of conflicting sets

is described by the elliptical sector obtained by intersecting the ellipsebound region

(c1)

2 + (c2)2 − 2c1c2ha1, a2i < r2

1,2

with the open octant c2 > c1 > 0, corresponding to the case when agent

1 is the one closer to the origin. In the other case (agent 2 is closer to

the origin), the corresponding elliptical sector is obtained by intersecting

(c1)

2 + (c2)2 − 2c1c2ha1, a2i < r2

2,1

with the octant c1 > c2 > 0. The role of the angle θ between the edges

e1, e2 in both sectors is the equality ha1, a2i = cos(θ). An example of

two such sectors is shown in Figure 2.

c2

c1

Figure 3. An example of two stripes in the c1c2-plane corresponding to

conflicting states of two agents on the same edge.

In each of the four cases listed in Remark 3.1, the respective continuous state coordinates x

1

μ

, x2

μ

of agents 1, 2 in control mode μ map to the

coefficients c1, c2, as follows:

1. If both agents are moving toward the common vertex, then x

α

μ =

l(eα) − cα for α = 1, 2.

2. If both agents are moving away from the common vertex, then

x

α

μ = cα for α = 1, 2.

7
3. If agent 1 is approaching, and agent 2 going away from, the common

vertex, then x

1

μ = l(e1) − c1, x2μ = c2.

4. If agent 2 is approaching, and agent 1 going away from, the common

vertex, then x

1

μ = c1, x2μ = l(e2) − c2.

If θ ≥ 90◦, then in the last two cases μ allows only one in-trail sequence,

so the minimal separations used for the two sectors in Figure 2 are equal.

If the two agents 1, 2 are on one and the same edge, then the set in the

c1c2-plane of the conflicting states appears as in Figure 3 (the asymmetry

about the dashed diagonal corresponds to (5). The mapping from the

continuous state coordinates x

1

μ

, x2

μ

to the coefficients c1, c2 is constructed

analogously to the above four cases.

1

2

2

1

(a) (b) (c)

Figure 4. An example of two agents whose paths in the transportation

network are prescribed and overlap. The black star shows the beginning

of the overlap in (a) and the corresponding state (both agents being

at that point) in (b); the white star, the end of the overlap in (a) and

the corresponding state (both agents being at that point) in (b). The

system, shown in (a), has seven control modes with both agents in the

transportation network. Each mode’s set of separation-violating states,

shown in (b) as a connected [23] gray region, is “glued” to some of the

others. The result of the gluing is the connected region shown in (c).

The above calculation is illustrated, for an example of two moving

agents, in Figure 4. In each control mode, the set of conflicting states is

shown as a connected [23] gray region. For dimension A above 2, one must

compute for each pair of agents the set of states violating the separation

requirements. Each such set is a cylinder, or union of cylinders, with the

base shaped as shown in Figure 4c, in the total state space ∪μXμ. We

note that the set of all separation-violating states in ∪μXμ is cylindrical

in the sense of [5, Definition 2.2], the latter definition a key requirement

for the applicability of a number of theoretical results of [5].

8
4 The Scheduled Routing Problem and the equivalent Stacked Scheduled Routing Problem

For ease of exposition, we precede the general formulation of the problem,

suitable for an arbitrary number of moving agents, with a specific, twoagent, example.

4.1 An instance of the scheduled routing problem for two

agents

e2

e1

e4

e6

e3

e5

e7

e8

2

1

e2

e1

e4

e6

e3

e5

e7

e8

2

1

2

1

(a) (b)

Figure 5. An initial state (a) and required destinations (b) of a two-agent

set.

The initial state of a two-agent scheduled routing is shown in Figure 5a;

the required destinations (with possibly different required arrival times)

for the two agents, in Figure 5b. In this Figure,

α = 1 : e

INIT;1 = e1, eDEST;1 = e8,

α = 2 : e

INIT;2 = e2, eDEST;2 = e7

The paths are

p1 : e1, e3, e6, e8; p2 : e1, e4, e8; p3 : e2, e3, e6, e7; p4 : e2, e4, e7 (8)

Agent 1 can take either p1 or p2; agent 2, either p3 or p4. Consequently,

P



e

INIT;1, eDEST;1

= {p1, p2}, P



e

INIT;2, eDEST;2

= {p3, p4}

No other paths can be taken.

9
e1 e6

e3 e8

e2

e4

e5

e7

e2

e1

e4

e6

e3

e5

e7

e8

(a) (b)

e2

e1

e4

e6

e3

e5

e7

e8

e2

e1

e4

e6

e3

e5

e7

e8

(c) (d)

Figure 6. The four paths (8), in that order, for the problem in Figure 5.

The paths p1, . . . , p4 are shown, in that order, in Figure 6. We obtain

the control modes μ1, . . . , μ4, defined as follows:

α μ1(α) μ2(α) μ3(α) μ4(α)

1 p1 p1 p2 p2

2 p3 p4 p3 p4

The state space corresponding to each control mode μ is a rectangle

consisting of those state vectors x

1

μ

, x2

μ



that are compliant with the

arc length bounds and separation constraints.

The above system is subject to the operational requirement (3), here

for α ∈ A = {1, 2}, that agents 1 and 2 arrive at their destinations at

times t

DEST;1, tDEST;2, respectively.

10
2

1

2

1

(a) (b)

Figure 7. Topology of approximated conflict zone in the state spaces (a)

Xμ1, Xμ4and (b) Xμ2, Xμ3. The black dot (near top right) denotes the

required destination coordinate pair x

DEST;1

μ

, xDEST;2

μ



.

In each of μ1, μ4, the pairwise conflict zone is simply connected [23]

(i.e., consists of only one connected component and has no “holes”).

Consequently, once each of the conflict zones, of the form shown in Figure

4c, is approximated by an ellipse-bounded region, the state spaces for

μ1, μ4 have the topology shown in Figure 7a. In each of μ2, μ3, the two

agents’ paths have two crossings (regarded here as short overlaps), hence

the pairwise conflict zone has two connected components (Figure 7b).

Each control mode μ is subject to the initial condition

x

α

μ

(0) = x

INIT;α

for α ∈ A (9)

The simplifying assumption underlying (9) is that both agents start their

journey simultaneously. This assumption can be relaxed and is used here

for mathematical simplicity only.

Finally, for each control mode μ, we can specify a cost functional

that suits the goals implied by the context of the specific application.

One example is a cost functional that requires the agents (e.g., trains)

to move as slowly as possible, for safety, is

X

α∈A

Z tDEST ;α

0



s

α

μ

2

dt (10)

Thus, for each control mode μ, we have an optimal control problem

with dynamical law (2), subject to the initial condition (9), the control

constraints that specify permissible value ranges for the speeds s

α

μ

, and

the following additional constraints:

• The arrival requirement (3).

• The separation requirement, defined by constructing a function

g

SEP;α1,α2

μ

((x

α

μ

)α∈A) of the state such that the pairwise conflict

11
zone (shown as a gray-shaded region in the appropriate panel of

Figure 7) is exactly the set of states satisfying the functions

g

SEP;α1,α2

μ ≥ r

2

α1,α2

, (11)

where each g

SEP;α1,α2 (xα1

, xα2 ) is a quadratic function of the form

given by the left-hand side of (7).

For the pair (α1 = 1, α2 = 2) (and, in the general scheduled routing

problem, for every pair (α1, α2)) of agents, inequality (11) defines a union

(denoted Xα1,α2

μ

) of regions in the state space of μ, each region bounded

by an ellipse-cylindrical (“tube-shaped”) hypersurface. The separation

requirement thus translates into the requirement that a solution (the

state trajectory) is disjoint from the interior of every such region for

every pair of agents.

4.2 The Scheduled Routing Problem: a general formulation

The central problem of this paper, which will be called the Scheduled

Routing Problem, can now be stated as follows.

Definition 4.1. (Scheduled Routing Problem) Given a set A of agents

moving on a route network G = (V, E) subject, in each control mode μ,

to the dynamical law (2), the initial condition (9), and the control constraints (4), find a control strategy (s

μ

α

(τ ))α such that the corresponding

state trajectory xμ(t) = (x

α

μ

(t))α∈A that satisfies (3) and minimizes the

total cost.

This is an optimal control problem with a Lagrange cost function.

The problem, however, has two non-standard features that hamper application of classical optimal control theory and numerical computation

of solutions. One feature is the presence of intermediate constraints.

The other is the following non-autonomous behavior: an agent, once at

destination, no longer “participates” in the constraints or in the cost.

We now use a formalism similar to that in [24] to reduce this problem

to a classical, optimal control problem, which is autonomous if its cost

functional is. In the rest of this section, the subscript μ is dropped for

brevity.

4.3 The Stacked Scheduled Routing Problem (SSRP), equivalent to the Scheduled Routing Problem

Let (αq)

A

q=1 be an ordering of the agents by their arrival times (arranged

in nondecreasing order). Let t0 = 0, and for each q > 0 let

tq = t

DEST;αq

Define a new (normalized) time τ ∈ [0, 1] and, for each of the intervals

[tq, tq+1], q = 0, . . . , A − 1, introduce the following:

12
• the state variable ρq(τ ), which will play the role of “physical time”

in the interval [tq, tq+1]:

tq ≤ ρq(τ ) ≤ tq+1;

• the state variables y

α

q

(τ ), α ∈ A, related to the above x

α(t) by

y

α

q

(τ ) = x

α

(t) if ρq(τ ) = t; (12)

• the vector notation yq(τ ) = (y

α

q

(τ ))α∈A;

• the control variables s

α

q

(τ ), related to the above s

α(t) by

s

α

q

(τ ) = s

α

(t) if ρq(τ ) = t, (13)

• the control variables zq > 0, which represent the rate of flow of

physical time with respect to the normalized time τ .

The above definition of the Lagrange cost reflects the assumption that

an agent, once at destination, “disappears” from the system, in the sense

of being no longer subject to the separation requirement with the other

agents. From (2), (12), and (13), one readily obtains the dynamical law

equations

d

dτ

y

αq′

q = zqs

αq′

q for q

′ ≥ q + 1

d

dτ

ρq = zq







α ∈ A (14)

Finally, the initial conditions and arrival requirement, together with the

requirement that physical time and state change continuously when passing from one interval [tq, tq+1] to the next, translate to the endpoint

constraints

y

α

0

(0) = x

INIT;α (see (9)) (a)

ρq(1) = ρq+1(0) (b)

ρq+1(0) = tq+1 (c)

y

αq′

q (1) = y

αq′

q+1(0) for q

′ ≥ q + 1 (d)

y

αq+1

q+1 (1) = x

DEST;αq+1 (e)







0 ≤ q < A (15)

Conditions (15.bc) ensure the continuity of physical time flow; conditions

(15.d), the continuity of an agent’s motion.

13
Remark 4.1. The state equations (14) and the endpoint constraints

(15.d) come with the restriction q

′ ≥ q + 1 because they are imposed,

in agreement with (2), only for those agents who have not yet reached

their destination: by the end of the q-th time period, the first q agents

have reached destination. Thus, upon reaching destination, an agent is

excluded from the model, and is no longer represented by a state equation

or subject to separation constraints with the other agents. This eliminates

the necessity to continue modeling an agent whose role in the model has

already been fulfilled.

Throughout the rest of this paper, the choice (10) of the cost functional is assumed in all the numerical examples. Other choices of the cost

functional are discussed in section 6. Since the time intervals between

each consecutive pair of arrivals are modeled, in this latter formulation,

as if they were occurring simultaneously (“stacked” upon one another),

the following definition will be adopted.

Definition 4.2. (a) The newly obtained optimal control problem corresponding to a control mode μ and consisting of the state equations (14),

endpoint constraints (15), cost functional (10), the separation constraints

on the variables y

αq′

q , the control constraints corresponding to (4) specifying the speed ranges on the variables s

αq′

q , and the positivity constraints

zq > 0,

will be called a μ-stacked optimal control problem.

(b) The set of all μ-stacked optimal control problems will be called a

Stacked Scheduled Routing Problem (SSRP).

(c) Of all the optimal solutions to all the μ-stacked optimal control

problems, a solution achieving a lowest cost is called an optimal solution

to the SSRP.

Thus, an SSRP consists of a collection of optimal control problems,

and an optimal solution to the SSRP tells not only how quickly the

agents are to move, but also how they should be routed. The SSRP is

equivalent to the Scheduled Routing Problem (definition 4.1).

4.4 Implications of the Pontryagin Maximum Principle

for the SSRP

The assumption that we are in a specific control mode μ is still in force.

Denote by ξyq, ξρqthe costates for yq, ρq. In those states where none of

the state constraints is active, the Hamiltonian for each control mode of

the SSRP is

H = −f0 +

X

q;q

′≥q+1

zqs

αq′

q ξyq +

X

q

zqξρq

,

14
where f0 is the performance index (running cost) corresponding to the

cost functional (10). Since H does not explicitly depend on any of the

state variables, it follows that the costate variables are constant along

the trajectory portions clear of state constraints and, consequently, the

maximization of H in each such state is a problem of static maximization.

This fact, in turn, implies the existence of an optimal state trajectory

in which these portions are rectilinear on each [tq, tq+1]. If, furthermore,

there is only one optimal trajectory, then its portions away from the

obstacle boundary are necessarily rectilinear.

With the state equations (2) and the set (4) of control constraints, the

set of all states reachable from a given state y

0

μ = (y

0;α

μ

)α∈A is the pointed

polyhedral cone that consists of all states yμ = (y

α

μ

)α∈A satisfying

0 ≤



y

α1

μ − y

0;α1

μ



s

MIN;α1

μ

s

MAX;α2

μ

≤ y

α2

μ − y

0;α2

μ

≤



y

α1

μ − y

0;α1

μ



s

MAX;α1

μ

s

MIN;α2

μ







α1 6= α2

This cone has vertex y

0

μ and is the intersection of the half-spaces

y

α2

μ − y

0;α2

μ ≤

sMAX;α1

μ

s

MIN;α2

μ



y

α1

μ − y

0;α1

μ



, α1 6= α2,

y

α2

μ − y

0;α2

μ ≥

sMIN;α1

μ

s

MAX;α2

μ



y

α1

μ − y

0;α1

μ



, α1 6= α2,

and

y

α

μ ≥ y

0;α

μ

, α ∈ A

The narrower the speed ranges (4), the narrower the cone, and the

smaller the portions of an optimal trajectory that lie on the boundary

of the obstacle

∪α16=α2X

α1,α2

μ

This suggests that, for narrow speed ranges, optimal trajectories for

the Stacked Scheduled Routing Problem can be well approximated by

piecewise linear curves.

4.5 An approach to computing solutions and an analysis

of the associated costs

The number of the control modes μ is the product

Y

α∈A





P



e

INIT;α

, eDEST;α







Paths which are, or contain, cycles are allowed in the model and can be

desirable in some applications; e.g., in air traffic models where aircraft

may be sent into a holding pattern to absorb delay. Furthermore, the

following holds true:

15
Remark 4.2. Every solution to the control problem described above will

correspond to exactly one of the control modes μ. This property of the

problem removes two difficulties associated inherently with hybrid systems

and absent from classical control systems, the risk of excessively frequent

switchings of control mode, and the necessity for “control mode memory,”

i.e. for keeping track of the control modes entered prior to the current

time in the system’s evolution.

Each set P



e

INIT;α, eDEST;α



can be computed using the DepthFirst Search algorithm, whose computational cost in a non-parallel implementation is known [15, section 23.3] to be O(|V | + |E|).

These considerations suggest the following procedure for finding an

optimal solution to an SSRP. Upper bounds on the computational cost

are provided, in square brackets ([]), where possible.

• Compute all the sets P



e

INIT;α, eDEST;α



. [In a non-parallel implementation, this computation amounts to a Depth-First Search

for each agent α ∈ A, hence the computational cost is O(|A|(|V |+

|E|)).]

• For each μ, compute an optimal solution to the corresponding

Stacked Scheduled Routing Problem, and the cost Cμ of that solution. [The computational cost depends on the particular choice of

the computational method; see, for example, [18, 25]. The numerical results in this paper were produced using Sequential Quadratic

Programming (SQP) [18], chosen for the convenience of available

software.]

• Select a control mode μ

∗

such that Cμ∗ ≤ Cμ for all μ, and declare

the corresponding optimal solution the optimal solution for the

SSRP (definition 4.2). [O(the number of control modes).]

5 Sample numerical computations for the Stacked

Scheduled Routing Problem

5.1 Assumptions and notational conventions

All the transportation networks appearing in the numerical examples

of this section are graphs; namely, no two vertices are connected by

more than one edge. This allows to specify each path as a sequence of

vertices, rather than of edges. To simplify the computations, the separation requirements for each pair of agents are assumed symmetric. The

numerical code admits a straightforward, albeit somewhat cumbersome

algebraically, generalization that will dispense with this assumption.

In panels (a, b) of Figures 9, 11, 12-17, the computed trajectories and

controls are plotted using the symbols described in Table 1. In panels

16
Quantities Plot symbol

y

1

q

, s1

q —

y

2

q

, s2

q +

y

3

q

, s3

q – –







for q = 1, . . . , A

Table 1. The legend used in Figures 9, 11, 12-16, below.

(c) (and, when present, (d)) of these Figures, as well as in Figures 8 and

10, the transportation networks are depicted as directed graphs; moving

agents, as points labeled with values of α, each point serving as a center

of a circle with radius equal to half the required pairwise separation. In

all plots, axis label ρ refers, in agreement with the above, to physical

time. All plots were generated using the MATLAB software [26].

The first two of the examples in section 5.4 are “abstract,” in the

sense that no particular application is specified for them. Thus, the units

of length and physical time are left unspecified. Application and units

are, however, specified for the third example. The required destination

y

DEST;α is in each case the end of the path assigned to agent α in control

mode μ:

y

DEST;α = 0

5.2 The cost function

The cost function used in the following examples is (10), which, on converting the scheduled routing problem to a Stacked Scheduled Routing

Problem (definition 4.2), takes the form

X

A

q=0

X

q

′≥q+1

Z 1

0



s

αq′

q

2

ρqdτ

5.3 Computational methods

In each control mode, the corresponding optimal control problem was

solved using the OCP solver [20], which uses Sequential Quadratic Programming (SQP) [18].

17
5.4 Numerical examples

5.4.1 Three moving agents, one control mode

−2 −1 0 1 2

−2

−1

0

1

2

 v1

 v2

 v3

 v4 v5

α = 1

α = 2

α = 3

Figure 8. The transportation network and the agents’ initial locations

in the example of section 5.4.1.

The transportation network for this example is the 2-dimensional directed graph shown, together with the three agents’ initial locations, in

Figure 8. Each agent can traverse only the edge on which it is positioned

initially, hence only one control mode μ arises.

The speed ranges are given by

α 1 2 3

sMIN;α

μ 0.3 0.3 0.4

sMAX;α

μ

1.5 0.8 0.9

The required times of arrival at destination are

α 1 2 3

t

DEST;α 2.0 3.0 4.0

The minimal required separation is 0.3.

The numerical solution computed for the control mode μ is shown in

Figure 9.

18
0 1 2 3 4 −2.5

−2

−1.5

−1

−0.5

0

0.5

ρ

the agents’ arc length coordinates

0 1 2 3 4 0.4

0.60.8

1

1.21.4

ρ

the agents’ speeds

(a) (b)

−2 −1

0 1 2 −2

−1

012

 v

1

 v

2

 v

3

 v

4 v

5

α = 1

α = 2

α = 3

−2 −1

0 1 2 −2

−1

012

 v

1

 v

2

 v

3

 v

4 v

5

α = 1

α = 2

(c) (d)

Figure 9. Numerical solutions (for the only possible control mode) in the example of section 5.4.1. (a) State 

(b) Control strategy vs. time. (c) The positions of the agents in the transportation network at

ρq(1) for q = 

of the agents in the transportation network at

ρq(1) for q = 2.

19
5.4.2 Two moving agents, four control modes, wide speed

ranges

−6 −4 −2 0 2 4 6 8 10

−12

−10

−8

−6

−4

−2

0

2

4

6

8

 v1

 v2

 v3 v4

 v5

 v6 v7

 v8

 v9

 v10

α = 1

α = 2

Initial state

Figure 10. The transportation network and the agents’ initial locations

in the example of section 5.4.2.

The transportation network for this example is the 2-dimensional directed graph shown, together with the two agents’ initial locations, in

Figure 10.

The two paths considered here are

p1 : v1, v2, v8, v9, v10, v6; p2 : v1, v2, v3, v4, v5, v6

The speed ranges are given by

α 1 2

sMIN;α

μ 0.6 0.6

sMAX;α

μ

1.4 1.4

The required times of arrival at destination are

α 1 2

t

DEST;α 28.3 36.1

The minimal required separation is 1.0.

The control modes are as follows.

α μ1(α) μ2(α) μ3(α) μ4(α)

1 p1 p2 p2 p1

2 p2 p1 p2 p1

20
0 5 10 15 20 25 30 35 40

−30−25−20−15−10

−5

05

ρ

the agents’ arc length coordinates

0 5 10 15 20 25 30 35 40

0.7560.758

0.76

0.7620.7640.7660.768

0.77

0.7720.7740.776

the agents’ speeds

ρ

2 3 4 5 6 

−2−1

012345678

 v

3

 v 

7

End of time interv

(a) (b) (c)

Figure 11. Numerical solutions for control mode

μ1 in the example of section 5.4.2. (a) State trajectory vs

strategy vs. time. (c) The positions of the agents in the transportation network at

ρq(1) for q = 1.

21
20 25 30 35 40

ρ

0 5 10 15 20 25 30 35 40 0.65 0.7 0.75 0.8 0.85 0.9 0.951

the agents’ speeds

ρ

2 3 4 5 6 7 8 9 10

−2−1

01234567 v3 v4

 v

 v 5 6 v7

 v8 v9

 v10

α = 1

α = 2

End of time interval #1: ρ = 28.3

(b) (c)

al solutions for control mode μ2 in the example of section 5.4.2. (a) State trajectory vs. time. (b) Control

) The positions of the agents in the transportation network at ρq(1) for q = 1.

22
0 5 10 15 20 25 30 35 40

−30−25−20−15−10

−5

05

ρ

the agents’ arc length coordinates

0 5 10 15 20 25 30 35 40

0.760.78

0.8

0.820.840.860.88

0.9

0.920.94

the agents’ speeds

ρ

2 3 4 5 6 

−2−1

012345678

 v

3 

 v

7

End of time interv

(a) (b) (c)

Figure 13. Numerical solutions for control mode

μ3 in the example of section 5.4.2. (a) State trajectory vs

strategy vs. time. (c) The positions of the agents in the transportation network at

ρq(1) for q = 1.

23
20 25 30 35 40

ρ

0 5 10 15 20 25 30 35 40 0.62 0.64 0.66 0.68 0.7 0.72 0.74 0.76 0.78 0.8

the agents’ speeds

ρ

2 3 4 5 6 7 8 9 10

−2−1

012345678

 v3 v4

 v v 5 6 v7

 v8

 v9

 v10

α = 1

α = 2

End of time interval #1: ρ = 28.3

(b) (c)

al solutions for control mode μ4 in the example of section 5.4.2. (a) State trajectory vs. time. (b) Control

) The positions of the agents in the transportation network at ρq(1) for q = 1.

24
The respective numerical solutions for these modes are shown in Figures 11-14.

The total costs for each control mode are as follows:

control mode μ1 μ2 μ3 μ4

total cost 37.5823 38.8925 45.4652 31.5979

Therefore, the optimal routing and control strategy are achieved in control mode μ4.

5.4.3 Two moving agents, four control modes, narrow speed

ranges

In this example, the transportation network, 3-dimensional, models a

terminal airspace, which consists of two arrival paths merging into the

same final approach segment. The transportation network and the initial

positions of the two aircraft are shown in Figure 15.

Here the edge (v6, v7) is the final approach to a runway, and the

moving agents are aircraft. For realism, one unit of arc length is taken

here to be 3 nautical miles, and the unit of speed is taken to be 200

knots, a typical speed allowed in U.S. terminal airspaces at altitudes

below 10, 000 feet.

The two paths considered here are

p1 : v1, v2, v8, v9, v10, v6; p2 : v1, v2, v3, v4, v5, v6

The control modes are as follows.

α μ1(α) μ2(α) μ3(α) μ4(α)

1 p1 p2 p2 p1

2 p2 p1 p2 p1

The speed ranges are given by

α 1 2

sMIN;α

μ

0.8 (= 160 kts) 0.8

sMAX;α

μ 1.2 (= 240 kts) 1.2

The required times of arrival at destination are

α 1 2

t

DEST;α 21.2 (= 0.03 hrs) 28.1 (= 0.04 hrs)

The minimal required separation is 1.0 (= 3 nmi).

25
−10

0

10

−10 −8 −6 −4 −2 0 2 4 6

 v3

 v4

 v7

 v5

 v2

 v6

 v10

 v9

 v8

α = 1

 v1

α = 2

mensional route network and the moving agents’ initial positions (centers of the circles in horizontal planes),

ample of section 5.4.3. Here the route network is a terminal airspace, and the agents are arriving aircraft. The

is half the minimal required pairwise separation of 3 nmi.

26
(a)

0 10 20 30 −30

−25

−20

−15

−10

−5

0

ρ

the agents’ arc length coordinates

(b)

0 10 20 30 0.95

1

1.05

ρ

the agents’ speeds

(c)

−5

0

5

10

−10 −8 −6 −4 −2 0

2

4

6

8

0

0.5

1

1.5

α = 2

α = 1

Figure 16. Numerical solutions for control mode μ1 in the example of

section 5.4.3. (a) State trajectory vs. time. (b) Control strategy vs.

time. (c) The positions of the agents in the transportation network at

ρq(1) for q = 1.

27
(a)

0 10 20 30 −25

−20

−15

−10

−5

0

5

ρ

the agents’ arc length coordinates

(b)

0 10 20 30 0.8

0.85

0.9

0.95

1

1.05

ρ

the agents’ speeds

(c)

−5

0

5

10

−10 −8 −6 −4 −2 0 2 4 6

0

0.2

0.4

0.6

0.8

1

1.2

1.4

α = 1

α = 2

Figure 17. Numerical solutions for control mode μ4 in the example of

section 5.4.3. (a) State trajectory vs. time. (b) Control strategy vs.

time. (c) The positions of the agents in the transportation network at

ρq(1) for q = 1.

28
In control modes μ2, μ3, the control problem has no solution, since

the path lengths are such that the imposed speed ranges prevent at least

one agent from reaching its destination at time. The numerical solution

for control mode μ1 is shown in Figure 16 and incurs a total cost of

49.2396. In μ4, the computed optimal control strategies prescribe the

constant speeds

s

1

μ4 = 1.03, s2μ4 = 0.82

and the solution (Figure 17) incurs a total cost of 41.5594. Therefore,

the optimal routing and control strategy are achieved in control mode

μ4.

6 Discussion

The above modeling framework addresses the problem of navigating a

set of moving agents in a transportation network, with constraints on

the agents’ initial locations, required destinations, and required times

of arrival at destination, as well as on the agents’ minimal pairwise distances. We now discuss several directions in which the above model can

be varied and generalized.

6.1 A model that includes inertia

Inertia can be included by treating both the y

α

μ

’s and the s

α

μ

’s as state

variables, and the accelerations a

α

μ

as the control variables. The corresponding new state equations would assume the form

y ̇

α

μ = s

α

μ

s ̇

α

μ = a

α

μ

)

, α ∈ A

The rescaling of physical time to normalized time τ ∈ [0, 1] formulated in

section 4.2 would be carried out analogously. The resulting problem falls

in the class of the kinodynamic motion planning problems; some related

theoretical results can be found in [5] and in references therein.

6.2 Different choices of the cost function

Of the vast number of possible choices of cost function, we briefly discuss

two.

• In situations where inertia cannot be neglected and acceleration

must be the control variable (or among the control variables), it

may be desirable to keep the movement as smooth as possible,

e.g., for passenger comfort or cargo safety. A cost function that

would serve this goal is the integral of the sum of the squared

accelerations:

X

α∈A

Z tDEST ;α

0



a

α

μ

2

dt

29
• In situations where it is undesirable to impose times t

DEST;α of arrival at destination as rigid constraints, and preferable to minimize

the absolute differences between the actual arrival times t

AAT;α.

This goal would be served by taking the sum

X

α∈A



t

DEST;α − tAAT;α

2

as the cost.

6.3 Asymmetric and anisotropic pairwise separation requirements

In some applications, the pairwise separation requirements for the moving agents can be asymmetric or anisotropic, or both. Such is the case

when the moving agents in question are aircraft traveling along their

nominal routes. An example of asymmetry is as follows. If two aircraft

are consecutively in-trail and at the same altitude, and the leader’s and

follower’s respective weight classes [22] are Heavy and Small, the required

separation is considerably larger than if the two engine types were in the

opposite order. An example of anisotropy is the requirement of vertical

separation between two aircraft, where aircraft are required to maintain

either 1000 ft vertical separation or the prescribed lateral separation previously discussed; the resultant shape of an aircraft’s safety envelope is a

cylinder. A mathematical form for such an anisotropic constraint would

use, not the Euclidean norm, but one of the following form: putting

ak = (a

x

k

, a

y

k

, az

k

), the norm in the left-hand side of (6) would be replaced

by a “mixed” norm, Euclidean in the xy-plane, and the max-norm along

the height z. If r were the minimal horizontal separation, imposed when

the two aircrafts’ altitudes differ by less than a quantity h, the mixed

norm and the corresponding separation constraint would be

||c1a1 − c2a2||mixed

:= max 

1

r

q

(c1a

x

1 − c2a

x

2

)

2 + (c1a

y

1 − c2a

y

2

)

2

,

1

h

|c1a

z

1 − c2a

z

2

|



≥ 1

The computations in section 3 would have to be modified accordingly

and would no longer have the closed quadratic form.

Acknowledgment

The authors thank D. Denery (NASA ARC) for suggesting the use of

hybrid systems for ATM, W. Haskell (USC) for editing early drafts of the

paper, H. Swenson (NASA ARC) and J. Mitchell (SUNY Stony Brook)

30
for helpful suggestions, O. Diallo (NASA ARC) for help with editing in

its final stages, and B. Fabien (University of Washington, Seattle) for

help with the use of the OCP solver [20].

References

1. Ghrist, R.; O’Kane, J. M.; and LaValle, S. M.: Computing Pareto

Optimal Coordinations on Roadmaps. The International Journal

of Robotics Research, vol. 24, no. 11, 2005, pp. 997–1010. URL

http://ijr.sagepub.com/content/24/11/997.abstract.

2. Luna, R. ans Bekris, K.: An efficient and complete approach for cooperative path-findin. National Conference on Artificial Intelligence

2, 2011, pp. 1804–1805.

3. Hu, J.; Prandini, M.; and Sastry, S.: Optimal coordinated motions

of multiple agents moving on a plane. SIAM J. Control and Optimization, vol. 42, 2003, pp. 637–668.

4. Hu, J.; Prandini, M.; and Tomlin, C.: Conjugate points in formation

constrained optimal multi-agent coordination: A case study. SIAM

J. Control, 2006.

5. Jung, J. B.; and Ghrist, R.: Pareto optimal multi-robot coordination

with acceleration constraints. Robotics and Automation, 2008. ICRA

2008. IEEE International Conference on, may 2008, pp. 1942 –1947.

6. Papadimitriou, C. H.; and Steiglitz, K.: Combinatorial Optimization; Algorithms and Complexity. Dover Publications, 1998.

7. Sussmann, H. J.: A maximum principle for hybrid optimal control

problems. The 38th IEEE Conference on Decision and Control, 1999,

pp. 425–430.

8. Mun ̃oz, L.; Sun, X.; Horowitz, R.; and Alvarez, L.: Traffic density

estimation with the cell transmission model. American Control Conference, 2003. Proceedings of the 2003, vol. 5, June 2003, pp. 3750

– 3755 vol.5.

9. Bayen, A. M.; Raffard, R. L.; and Tomlin, C. J.: Network Congestion Alleviation Using Adjoint Hybrid Control: Application to

Highways. Hybrid Systems: Computation and Control, R. Alur and

G. J. Pappas, eds., Springer Berlin / Heidelberg, vol. 2993 of Lecture

Notes in Computer Science, 2004, pp. 113–129.

10. Sastry, S.; Meyer, G.; Tomlin, C.; Lygeros, J.; Godbole, D.; and

Pappas, G.: Hybrid control in air traffic management systems. Decision and Control, 1995., Proceedings of the 34th IEEE Conference

on, vol. 2, Dec. 1995, pp. 1478 –1483 vol.2.

31
11. Hwang, I.; Balakrishnan, H.; and Tomlin, C.: State estimation for

hybrid systems: applications to aircraft tracking. Control Theory

and Applications, IEEE Proceedings -, vol. 153, no. 5, 2006, pp. 556

– 566.

12. Bayen, A.; and Tomlin, C.: Real-time discrete control law synthesis

for hybrid systems using MILP: application to congested airspace.

American Control Conference, 2003. Proceedings of the 2003, vol. 6,

June 2003, pp. 4620–4626.

13. Shilov, G.: Elementary Functional Analysis. Dover, 2nd ed., 1996.

14. Korn, G.; and Korn, T.: Mathematical Handbook for Scientists and

Engineers: Definitions, Theorems, and Formulas for Reference and

Review. McGraw-Hill, New York, 1961.

15. Cormen, T.; Leiserson, C.; and Rivest, R.: Introduction to Algorithms. The MIT Press, Cambridge, MA, 1990.

16. Boltyanskii, V.; Gamkrelidze, R.; Mishchenko, E.; and Pontryagin,

L.: Mathematical Theory of Optimal Processes. John Wiley & Sons,

Inc., 1962.

17. Bellman, R.: Dynamic Programming. Dover, 2003.

18. Pytlak, R.: Numerical Methods for Optimal Control Problems with

State Constraints. Springer, 1999.

19. Sethian, J.; and Vladimirsky, A.: Ordered Upwinds Methods for Hybrid Control. Proceedings Fifth International Conference on Hybrid

Systems and Control, LCNS 2289, 2002.

20. Fabien, B. C.: Implementation of an algorithm for the direct solution of optimal control problems. ASME 2011 International Design

Engineering Technical Conferences, 2011.

21. Rao, V. N.; and Kumar, V.: Parallel Depth First Search, Part

I: Implementation. International Journal of Parallel Programming,

vol. 16, 1987, pp. 6–479.

22. Radar Separation Minima. Order JO 7110.65T, Air Traffic Control,

FAA, 5, 2010.

23. Adams, C.; and Franzosa, R.: Introduction to topology: pure and

applied. Pearson Prentice Hall, 2008.

24. Dmitruk, A.; and Kaganovich, A.: Maximum principle for optimal control problems with intermediate constraints. Computational Mathematics and Modeling, vol. 22, 2011, pp. 180–215.

10.1007/s10598-011-9096-8.

32
25. Sethian, J. A.; and Vladimirsky, A.: Ordered Upwind Methods for

Static Hamilton-Jacobi Equations: Theory and Algorithms. SIAM

J. Numerical Analysis, 2003, pp. 325–363.

26. MATLAB: version 7.7.0.471 (R2008b). The MathWorks Inc., 2010.

33
REPORT DOCUMENTATION PAGE Form Approved

OMB No. 0704–0188

The public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources,

gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection

of information, including suggestions for reducing this burden, to Department of Defense, Washington Headquarters Services, Directorate for Information Operations and Reports

(0704-0188), 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be

subject to any penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number.

PLEASE DO NOT RETURN YOUR FORM TO THE ABOVE ADDRESS.

Standard Form 298 (Rev. 8/98)

Prescribed by ANSI Std. Z39.18

1. REPORT DATE (DD-MM-YYYY)

01-07-2012

2. REPORT TYPE

Technical Memorandum

3. DATES COVERED (From - To)

4. TITLE AND SUBTITLE

Optimal routing and control of multiple agents moving in a transportation

network and subject to an arrival schedule and separation constraints

5a. CONTRACT NUMBER

5b. GRANT NUMBER

5c. PROGRAM ELEMENT NUMBER

5d. PROJECT NUMBER

5e. TASK NUMBER

5f. WORK UNIT NUMBER

6. AUTHOR(S)

A. V. Sadovsky and D. Davis and D. R. Isaacson

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)

NASA Ames Research Center

Moffett Field, California 94035-0001

8. PERFORMING ORGANIZATION

REPORT NUMBER

L–¡ARC L-number¿

9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES)

National Aeronautics and Space Administration

Washington, DC 20546-0001

10. SPONSOR/MONITOR’S ACRONYM(S)

NASA

11. SPONSOR/MONITOR’S REPORT

NUMBER(S)

NASA/TM–2012–216032

12. DISTRIBUTION/AVAILABILITY STATEMENT

Unclassified-Unlimited

Subject Category 03

Availability: NASA CASI (443) 757-5802

13. SUPPLEMENTARY NOTES

An electronic version can be found at http://ntrs.nasa.gov.

14. ABSTRACT

We address the problem of navigating a set of moving agents, e.g. automated guided vehicles, through a transportation

network so as to bring each agent to its destination at a specified time. Each pair of agents is required to be separated by a

minimal distance, generally agent-dependent, at all times. The speed range, initial position, required destination, and

required time of arrival at destination for each agent are assumed provided. The movement of each agent is governed by a

controlled differential equation (state equation). The problem consists in choosing for each agent a path and a control

strategy so as to meet the constraints and reach the destination at the required time. This problem arises in various fields of

transportation, including Air Traffic Management and train coordination, and in robotics. The main contribution of the

paper is a model that allows to recast this problem as a decoupled collection of problems in classical optimal control and is

easily generalized to the case when inertia cannot be neglected. Some qualitative insight into solution behavior is obtained

using the Pontryagin Maximum Principle. Sample numerical solutions are computed using a numerical optimal control solver.

15. SUBJECT TERMS

multi-agent coordination, transportation network, roadmap, motion planning, optimal control, multigraph

16. SECURITY CLASSIFICATION OF:

a. REPORT

U

b. ABSTRACT

U

c. THIS PAGE

U

17. LIMITATION OF

ABSTRACT

UU

18. NUMBER

OF

PAGES

40

19a. NAME OF RESPONSIBLE PERSON

STI Help Desk (email: help@sti.nasa.gov)

19b. TELEPHONE NUMBER (Include area code)

(443) 757-5802