Page 44 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 44
of the first results on the successful application of LTL TN
in vehicle routing is [9], where the computation task is writ-
ten as a network flow problem with constraints. In [10], an J(x, u) = (|xi(k) − xti| + |yi(k) − yti|), subject to
incremental algorithm is given for the complex path plan-
ning of a single robot, where the specifications are given k=1 i=1
using LTL. A motion planning method for multiple agents
is presented in [11], where STL is used for describing specifi- the collision, obstacle-avoidance and possible additional con-
cations, taking into consideration imperfect communication
channels, too. straints, where xti and yti denote the prescribed target co-
ordinates corresponding to agent i.
The above results motivated us to use STL in our work for
route planning. The main novelty of our approach is the 3. ONLINE ROUTE PLANNING BY TEM-
division of the computation into two levels which allows us
to handle a relatively long prediction horizon with a singifi- PORAL LOGIC CONSTRAINED OPTI-
cantly reduced computation time.
MIZATION
2. PROBLEM FORMULATION
Based on the problem formulation above, it can be clearly
The problem is to plan and track routes for multiple AGVs, seen, that solving the routing problem requires at least 4N T
each of which is assumed to move in a two dimensional closed variables, with O(2N 2) + O(4N M ) constraints, resulting
space, independently in the x and y directions. All agents from vehicle-vehicle collisions and obstacle avoidance respec-
have upper bounds for speed and velocity, respectively. Each tively. Feasibility of obtaining solution in real-time is highly
agent has a target point assigned before running the plan- dependent on the applied solver, and on the constraints
ning algorithm. The objective for each agent is reaching its themselves.
target point in minimal possible time, without colliding with
obstacles or with each other. Our experiments showed that the problem scales badly when
the number of agents or the number of obstacles is increased.
Let N be the number of agents. On the low level, we model To overcome the issue, a two phase planning is proposed.
the agents as simple mass-points in a two dimensional carte-
sian coordinates system. Therefore, the motion of each agent The double-integrator model is used only in the second phase,
can be described in continuous time as two double integra- when a O(2 ∗ N 2) part of the constraints can be omitted.
tors with acceleration command inputs, resulting in 4N state Moreover, the second phase can be run individually for all
variables (coordinates and velocities), and 2N inputs. This agents, each having only 4T state variables and only 4M con-
model is discretized in time using a uniform sampling time straints resulting from obstacle avoidance (although some
ts. Let xi(k) and yi(k) denote the x and y coordinates of the constraints for following the first-phase must be added, as
ith robot at time step k, respectively. The inputs for agent described below).
i at time step k are denoted by uxi(k) and uyi(k) along the
x and y coordinates, respectively. 3.1 First phase planning
The borders of the environment, as well as the rectangle- In the first phase, a coarse route is designed with a relatively
shaped obstacles can be introduced as simple constraints large sampling time ts(1) to have as short prediction horizon
for the xi and yi state variables. Let the number of obsta- as possible. Moreover, only the coordinates of the agents
cles be M , each obstacle being defined by its lower-left and are taken into consideration, and the computed input (u¯xi,
upper-right corners (a1(l), b1(l)) and (a2(l), b2(l)). This means u¯yi) is the required coordinate change in each direction for
that avoiding obstacles can be written as a set of linear con- agent i in each time step. This results in simpler dependency
straints: between the input and the desired output, and considerably
reduces the required computation time.
{xi < a(1l) or xi > a2(l) or yi < b1(l) or yi > b(2l), ∀ i, l}
xi(k + 1) = xi(k) + u¯xi(k) i = 1...N
Collision-aviodance between agents is realized using a thresh-
old value δ and the constraints |xi(k) − xj(k)| > δ ∀ i = yi(k + 1) = yi(k) + u¯yi(k)
j. Note that due to the discrete-time model, this thresh-
old must be carefully chosen considering maximum vehicle |u¯xi(k)| < K
speed.
|u¯yi(k)| < K
The planning itself is run on a finite time horizon, consisting
of T steps. It is assumed, that all vehicles can reach their where K is an upper bound for coordinate changes which is
goal state within this time (given a reasonably large T ). determined using the maximum speed of the vehicle and the
However, the computation should work even if some of them sampling time ts.
is not able to fulfil this constraint.
The description of the rules for such a simple system is
The optimization problem is minimizing the following ob- quite straightforward using temporal logic. Given a rect-
jective function: angle shaped obstacle as defined above, the STL formula for
avoidance looks like:
[0,T ] xi < a1(l) or xi > a2(l) or yi < b(1l) or yi > b(2l)
. For avoiding collisions between the vehicles, we use:
[0T ] (|yi(t) − yj (t)| > dist or |xi(t) − xj (t)| > dist)
. (Here, the notation is the so-called always operator,
which means, that the formula must be true in all time in-
stants in the interval [1, T ] - which is the whole time of the
planning in our case.)
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 44
Koper, Slovenia, 10 October
in vehicle routing is [9], where the computation task is writ-
ten as a network flow problem with constraints. In [10], an J(x, u) = (|xi(k) − xti| + |yi(k) − yti|), subject to
incremental algorithm is given for the complex path plan-
ning of a single robot, where the specifications are given k=1 i=1
using LTL. A motion planning method for multiple agents
is presented in [11], where STL is used for describing specifi- the collision, obstacle-avoidance and possible additional con-
cations, taking into consideration imperfect communication
channels, too. straints, where xti and yti denote the prescribed target co-
ordinates corresponding to agent i.
The above results motivated us to use STL in our work for
route planning. The main novelty of our approach is the 3. ONLINE ROUTE PLANNING BY TEM-
division of the computation into two levels which allows us
to handle a relatively long prediction horizon with a singifi- PORAL LOGIC CONSTRAINED OPTI-
cantly reduced computation time.
MIZATION
2. PROBLEM FORMULATION
Based on the problem formulation above, it can be clearly
The problem is to plan and track routes for multiple AGVs, seen, that solving the routing problem requires at least 4N T
each of which is assumed to move in a two dimensional closed variables, with O(2N 2) + O(4N M ) constraints, resulting
space, independently in the x and y directions. All agents from vehicle-vehicle collisions and obstacle avoidance respec-
have upper bounds for speed and velocity, respectively. Each tively. Feasibility of obtaining solution in real-time is highly
agent has a target point assigned before running the plan- dependent on the applied solver, and on the constraints
ning algorithm. The objective for each agent is reaching its themselves.
target point in minimal possible time, without colliding with
obstacles or with each other. Our experiments showed that the problem scales badly when
the number of agents or the number of obstacles is increased.
Let N be the number of agents. On the low level, we model To overcome the issue, a two phase planning is proposed.
the agents as simple mass-points in a two dimensional carte-
sian coordinates system. Therefore, the motion of each agent The double-integrator model is used only in the second phase,
can be described in continuous time as two double integra- when a O(2 ∗ N 2) part of the constraints can be omitted.
tors with acceleration command inputs, resulting in 4N state Moreover, the second phase can be run individually for all
variables (coordinates and velocities), and 2N inputs. This agents, each having only 4T state variables and only 4M con-
model is discretized in time using a uniform sampling time straints resulting from obstacle avoidance (although some
ts. Let xi(k) and yi(k) denote the x and y coordinates of the constraints for following the first-phase must be added, as
ith robot at time step k, respectively. The inputs for agent described below).
i at time step k are denoted by uxi(k) and uyi(k) along the
x and y coordinates, respectively. 3.1 First phase planning
The borders of the environment, as well as the rectangle- In the first phase, a coarse route is designed with a relatively
shaped obstacles can be introduced as simple constraints large sampling time ts(1) to have as short prediction horizon
for the xi and yi state variables. Let the number of obsta- as possible. Moreover, only the coordinates of the agents
cles be M , each obstacle being defined by its lower-left and are taken into consideration, and the computed input (u¯xi,
upper-right corners (a1(l), b1(l)) and (a2(l), b2(l)). This means u¯yi) is the required coordinate change in each direction for
that avoiding obstacles can be written as a set of linear con- agent i in each time step. This results in simpler dependency
straints: between the input and the desired output, and considerably
reduces the required computation time.
{xi < a(1l) or xi > a2(l) or yi < b1(l) or yi > b(2l), ∀ i, l}
xi(k + 1) = xi(k) + u¯xi(k) i = 1...N
Collision-aviodance between agents is realized using a thresh-
old value δ and the constraints |xi(k) − xj(k)| > δ ∀ i = yi(k + 1) = yi(k) + u¯yi(k)
j. Note that due to the discrete-time model, this thresh-
old must be carefully chosen considering maximum vehicle |u¯xi(k)| < K
speed.
|u¯yi(k)| < K
The planning itself is run on a finite time horizon, consisting
of T steps. It is assumed, that all vehicles can reach their where K is an upper bound for coordinate changes which is
goal state within this time (given a reasonably large T ). determined using the maximum speed of the vehicle and the
However, the computation should work even if some of them sampling time ts.
is not able to fulfil this constraint.
The description of the rules for such a simple system is
The optimization problem is minimizing the following ob- quite straightforward using temporal logic. Given a rect-
jective function: angle shaped obstacle as defined above, the STL formula for
avoidance looks like:
[0,T ] xi < a1(l) or xi > a2(l) or yi < b(1l) or yi > b(2l)
. For avoiding collisions between the vehicles, we use:
[0T ] (|yi(t) − yj (t)| > dist or |xi(t) − xj (t)| > dist)
. (Here, the notation is the so-called always operator,
which means, that the formula must be true in all time in-
stants in the interval [1, T ] - which is the whole time of the
planning in our case.)
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 44
Koper, Slovenia, 10 October
