Signal Processing - November 2016 - 76
liveness. However, as will be discussed later in this article,
the partial lack of formal analysis tools limits their practical
applicability. In particular, the impact of imperfect sensing
data and communication impairments on stability and feasibility (i.e., the capability of finding a solution that meets safety
and liveness requirements) of (1) is not completely understood
under realistic communication protocols and sensing scenarios.
In the absence of sensing and communication impairments,
a simplified version of the generic problem (1) can be specified
mathematically as follows.
Safety constraints
Consider a set of N vehicles (agents), whose motion is
described by
xo i (t) = fi (x i (t), u i (t), t),
(2)
where x i ! X i 3 R n and u i ! U i 3 R m are the state and input/
control vectors, respectively, xo i (t) denotes the time derivative of x i (t) , and the sets X i, U i reflect physical and design
constraints. Examples of such constraints are acceleration
limitations and the vehicles' minimum and maximum speeds.
Examples of the state x i are vectors comprising the vehicle's
position and velocity in one, two, or three dimensions. Let
G i (x i) describe the vehicle geometry, being the closed and
compact set of spatial coordinates that vehicle i occupies when
its state is x i . Hence, a collision between two vehicles i and j
occurs at time t if
G i (x i (t)) + G j (x j (t)) ! 4.
(3)
Furthermore, we denote by C i the closed and connected set
of spatial coordinates that comprises the paths of vehicle i so
that a vehicle is on its path if G i (x i (t)) 3 C i . Provided that
each vehicle stays on its path, a collision between vehicles can
consequently only take place within a critical region where
Ci + Cj , i.e., where paths fully or partly overlap (i.e., where
paths are the same, cross, or merge).
Liveness constraints
Assume that all paths Ci are fixed and constant, and let the
target set Ti 1 Ci be the set of spatial coordinates that vehicle
i strives to reach (e.g., the road after an intersection, roundabout, or onramp). If G i (x i (t)) 1 Ti is satisfied in finite time
for all vehicles, the coordination is said to be deadlock-free,
and all vehicles are eventually coordinated through the critical regions. For an illustration of the introduced notations,
see Figure 2.
Performance criterion
In general, the cost for vehicle i, denoted by J i (x i (t), u i (t)) ,
can be expressed as
+3
#
J i (x i (t), u i (t)) =
K i (x i (t), u i (t), t) dt,
0
where the stage cost K i (x i (t), u i (t), t) could be, e.g., instantaneous power consumption so that J i (x i (t), u i (t)) is the total
consumed energy. Other examples of K i (x i (t), u i (t), t) include
a deviation from a target speed, or a measure of discomfort for
the driver.
Overall problem and its receding horizon formulation
2 (x
2 (t
))
With the introduced notations and concepts, the N-vehicle
optimal coordination problem (OCP) is now naturally formulated as the following infinite time, constrained optimal control problem.
G
Problem 1: OCP
minimize
x (t), u (t)
Γ1
Γ1 ∩ Γ2
(4b)
x i (t) ! X i, u i (t) ! U i
(4c)
Γ2
intersection. The geometries of vehicles 1 and 2 are highlighted in red, and
their paths C i are dashed and colored. The critical region, C 1 + C 2 , is shown
in dashed red, the target sets T1, T2 in green, and the paths before the critical region in yellow. The vehicle geometry G i (x i (t)) , depending on the
vehicle state x i (t) , is also depicted.
76
(4a)
i= 1
subject to xo i (t) = fi (x i (t), u i (t), t), x i (0) = x i, 0
G1(x1 (t ))
Figure 2. An example of a traffic coordination scenario at a three-way
N
/ J i (x i (t), u i (t))
G i (x i (t)) 3 C i
(4d)
G i (x i (t)) + G j (x j (t)) = 4, 6t $ 0, i, j ! i
(4e)
7 T 1 3 : G i (x i (T )) 3 Ti,
(4f)
where x (t) = [x T1 (t), ..., x TN (t)] T , u (t) = [u T1 (t), ..., u TN (t)] T represent the states and control signal for each vehicle over the
entire operating horizon (i.e., all t $ 0 ). The OCP is thus the
problem of finding the best admissible control inputs u i (t) for
the dynamical systems fi (x i (t), u i (t), t) (4b), starting from the
initial conditions x i, 0 , that respect the state constraints (4c),
while keeping all vehicles i within their paths Ci (4d), avoiding collisions between vehicles (4e), and eventually clearing
IEEE SIgnal ProcESSIng MagazInE
|
November 2016
|
Table of Contents for the Digital Edition of Signal Processing - November 2016
Signal Processing - November 2016 - Cover1
Signal Processing - November 2016 - Cover2
Signal Processing - November 2016 - 1
Signal Processing - November 2016 - 2
Signal Processing - November 2016 - 3
Signal Processing - November 2016 - 4
Signal Processing - November 2016 - 5
Signal Processing - November 2016 - 6
Signal Processing - November 2016 - 7
Signal Processing - November 2016 - 8
Signal Processing - November 2016 - 9
Signal Processing - November 2016 - 10
Signal Processing - November 2016 - 11
Signal Processing - November 2016 - 12
Signal Processing - November 2016 - 13
Signal Processing - November 2016 - 14
Signal Processing - November 2016 - 15
Signal Processing - November 2016 - 16
Signal Processing - November 2016 - 17
Signal Processing - November 2016 - 18
Signal Processing - November 2016 - 19
Signal Processing - November 2016 - 20
Signal Processing - November 2016 - 21
Signal Processing - November 2016 - 22
Signal Processing - November 2016 - 23
Signal Processing - November 2016 - 24
Signal Processing - November 2016 - 25
Signal Processing - November 2016 - 26
Signal Processing - November 2016 - 27
Signal Processing - November 2016 - 28
Signal Processing - November 2016 - 29
Signal Processing - November 2016 - 30
Signal Processing - November 2016 - 31
Signal Processing - November 2016 - 32
Signal Processing - November 2016 - 33
Signal Processing - November 2016 - 34
Signal Processing - November 2016 - 35
Signal Processing - November 2016 - 36
Signal Processing - November 2016 - 37
Signal Processing - November 2016 - 38
Signal Processing - November 2016 - 39
Signal Processing - November 2016 - 40
Signal Processing - November 2016 - 41
Signal Processing - November 2016 - 42
Signal Processing - November 2016 - 43
Signal Processing - November 2016 - 44
Signal Processing - November 2016 - 45
Signal Processing - November 2016 - 46
Signal Processing - November 2016 - 47
Signal Processing - November 2016 - 48
Signal Processing - November 2016 - 49
Signal Processing - November 2016 - 50
Signal Processing - November 2016 - 51
Signal Processing - November 2016 - 52
Signal Processing - November 2016 - 53
Signal Processing - November 2016 - 54
Signal Processing - November 2016 - 55
Signal Processing - November 2016 - 56
Signal Processing - November 2016 - 57
Signal Processing - November 2016 - 58
Signal Processing - November 2016 - 59
Signal Processing - November 2016 - 60
Signal Processing - November 2016 - 61
Signal Processing - November 2016 - 62
Signal Processing - November 2016 - 63
Signal Processing - November 2016 - 64
Signal Processing - November 2016 - 65
Signal Processing - November 2016 - 66
Signal Processing - November 2016 - 67
Signal Processing - November 2016 - 68
Signal Processing - November 2016 - 69
Signal Processing - November 2016 - 70
Signal Processing - November 2016 - 71
Signal Processing - November 2016 - 72
Signal Processing - November 2016 - 73
Signal Processing - November 2016 - 74
Signal Processing - November 2016 - 75
Signal Processing - November 2016 - 76
Signal Processing - November 2016 - 77
Signal Processing - November 2016 - 78
Signal Processing - November 2016 - 79
Signal Processing - November 2016 - 80
Signal Processing - November 2016 - 81
Signal Processing - November 2016 - 82
Signal Processing - November 2016 - 83
Signal Processing - November 2016 - 84
Signal Processing - November 2016 - 85
Signal Processing - November 2016 - 86
Signal Processing - November 2016 - 87
Signal Processing - November 2016 - 88
Signal Processing - November 2016 - 89
Signal Processing - November 2016 - 90
Signal Processing - November 2016 - 91
Signal Processing - November 2016 - 92
Signal Processing - November 2016 - 93
Signal Processing - November 2016 - 94
Signal Processing - November 2016 - 95
Signal Processing - November 2016 - 96
Signal Processing - November 2016 - 97
Signal Processing - November 2016 - 98
Signal Processing - November 2016 - 99
Signal Processing - November 2016 - 100
Signal Processing - November 2016 - 101
Signal Processing - November 2016 - 102
Signal Processing - November 2016 - 103
Signal Processing - November 2016 - 104
Signal Processing - November 2016 - 105
Signal Processing - November 2016 - 106
Signal Processing - November 2016 - 107
Signal Processing - November 2016 - 108
Signal Processing - November 2016 - 109
Signal Processing - November 2016 - 110
Signal Processing - November 2016 - 111
Signal Processing - November 2016 - 112
Signal Processing - November 2016 - 113
Signal Processing - November 2016 - 114
Signal Processing - November 2016 - 115
Signal Processing - November 2016 - 116
Signal Processing - November 2016 - 117
Signal Processing - November 2016 - 118
Signal Processing - November 2016 - 119
Signal Processing - November 2016 - 120
Signal Processing - November 2016 - 121
Signal Processing - November 2016 - 122
Signal Processing - November 2016 - 123
Signal Processing - November 2016 - 124
Signal Processing - November 2016 - 125
Signal Processing - November 2016 - 126
Signal Processing - November 2016 - 127
Signal Processing - November 2016 - 128
Signal Processing - November 2016 - 129
Signal Processing - November 2016 - 130
Signal Processing - November 2016 - 131
Signal Processing - November 2016 - 132
Signal Processing - November 2016 - 133
Signal Processing - November 2016 - 134
Signal Processing - November 2016 - 135
Signal Processing - November 2016 - 136
Signal Processing - November 2016 - 137
Signal Processing - November 2016 - 138
Signal Processing - November 2016 - 139
Signal Processing - November 2016 - 140
Signal Processing - November 2016 - 141
Signal Processing - November 2016 - 142
Signal Processing - November 2016 - 143
Signal Processing - November 2016 - 144
Signal Processing - November 2016 - 145
Signal Processing - November 2016 - 146
Signal Processing - November 2016 - 147
Signal Processing - November 2016 - 148
Signal Processing - November 2016 - Cover3
Signal Processing - November 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com