Page 128 - Innovations in Intelligent Machines

Evolution-based Dynamic Path Planning for Autonomous Vehicles 119
planning algorithm by using a stochastic model. The model presented here is
for 2-dimension problems, but it can be extended to 3-dimension problems.
The system considered here consists of a vehicle and its environment. We call
this system the world. The vehicle is assigned to perform N T tasks.
For a planning time horizon t N , the world model used to predict future
states during the time t k <t ≤ t N can be written in a discrete form as
x(q +1) = f(x(q),u(q)), q = k, k +1,...,N − 1 (1)

where f is the state transition function, x is the state vector of the system
V
E
which includes states of the vehicle x , states of the environment x ,and
F T
V
F
E
task states x . That is x =[x ,x ,x ] . We assume that the information of
E
all states at time t k is available to the planner except x which is known with
a limited level of certainty. In the following equations, the expected value of
y
a random variable y will be simply written as ˜.
F
The state of each task i, x , indicates whether the task is completed;
i
x F = 1 when the task is initially assigned, and x F = 0 if it is completed.
i
i
V
V
The states of the vehicle consists of its position z ,velocity ˙z , and health
V T
V
V
V
V
state ξ . That is x =[z , ˙z ,ξ ] . The health state indicates if the vehicle
is intact or destroyed; ξ V = 1 if the vehicle is intact, and ξ V = 0 if it is
destroyed.
We define sites as any objects in the environment. The states of the envi-
ronment are the states of all the sites. Obstacles are special types of sites with
ability to change the states of vehicles if they become in contact. A target is
defined as a site in the environment associated with a task. Thus, a site can
be a target and an obstacle simultaneously, or it can be neither. The number
of obstacles N O plus the number of targets N G is not necessary equal to the
number of all the sites N S . The states of the environment are composed of
E
the position z , velocities ˙z E and health states ξ E of all the sites. That is
E
E T
E
E
x =[z , ˙z ,ξ ] . The health state of site j indicates whether the site exists
E
E
or not; ξ = 1 if the site exists, and ξ = 0 if it does not exist.
j j
V
z
The input to the vehicle u includes a commanded position ¯ and a com-
¯ V
manded velocity ˙z ¯ V of the vehicle, and a task assignment vector d . That is
V ¯ V ¯ V T
z
u =[¯ , ˙z , d ] . Given a trajectory Q(s p−1 ) previously computed at time
, the commanded position and velocity while t q ∈ (t k ,t N ] are given by
t s p−1
V
¯ z (q)= h x (Q(s p−1 ),q) (2)
¯ V
˙ z (q)= h v (Q(s p−1 ),q)
where Q represents the set of parameters needed to define the planned trajec-
tory. The mapping functions h x and h v ,and Q, depend on how the trajectory
is encoded. The task assignment vector d ¯ V is a N T × 1 vector whose element

F
i is equal to one if x − x > 0, otherwise it is zero.
F
ref,i i
Using the following equations, we describe the stochastic model used to pre-
T
V ˜ V ˜ V
E ˜ E ˜ E
z
dict the expected values of all system states ˜x = ˜ , ˙z , ξ , ˜z , ˙z , ξ , ˜x F .