Page 45 - 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. 45
Second phase planning 5
The double-integrator model for the agents is used in thesecond phase, where we assume, that agent i has a source
and a target point, as well as a set of intermediary route 4
points Pi = {(xpi, ypi)|p = 1...T − 1} known from the pre-
vious phase. The planning is done using a rolling horizon 3 .approach, using a smaller sampling time ts(2) = ts(1)/k, k > 1.
In the simplest case this means that at route point p, the 2
p + 2-th point is set as a target. We use a temporal logic
formula to ensure that the agent will be in the prescribed 1
proximity of the point p + 1, and planning is done on a hori-
zon of T2 = 2 · k. This can be easily extended to include 12345
more intermediary route points. This planning step is re-
peated when the agent reaches the route point p + 1. It can Figure 1: Distances kept by the agents during the
be shown, that by choosing this ∆ proximity correctly, we first and second phase planning
can guarantee, that no collision between the agents can oc-
cur. The concept of the proof is that if the distance threshold taking into consideration the obstacles and vehicle-vehicle
from the first phase is equal to the half of the distance, an interactions as well. The algorithm calculates a set of con-
agent can move in the rough plan in one step (δ = K/2), and secutive intermediary route points for each agent, ensuring
we restrict the agents to remain in the ∆ = δ/2 proximity conflict-free behavior provided that agents are in the given
of the given point for the respective time interval, then the proximity of the points for the respective time interval. In
agents are always located inside different non-overlapping the second phase, each agent computes its own path, con-
δ × δ-sized squares. The concept is illustrated in Figure 1. sidering the points and intervals given in the first phase.
Thus, vehicle-vehicle interactions need not to be checked on
4. ILLUSTRATIVE EXAMPLE the detailed planning level, only smooth maneuvering and
obstacle avoidance between the points are required.
In order to illustrate the concept, a case study containing
ten agents was carried out. As it is visible in Fig. 2, we Acknowledgements
have a 16 × 10 units floorplan, containing 7 obstacles that
must be avoided. The first-phase planning is running on a This work has been supported by the research program titled
40 step long horizon, which means at least 10 × 40 × 2 = 800 ”Exploring the Mathematical Foundations of Artificial In-
continuous variables (x and y directions for all agents and telligence” (2018-1.2.1-NKP-00008). The partial support of
all discrete time points). The number of temporal logic for- the projects GINOP-2.3.2-15-2016-00002 and EFOP-3.6.3-
mulas is 10 × 7 (obstacles) + 10 × 9/2 (collisions) = 115, VEKOP-16-2017-00002 is also acknowledged. T. P´eni is the
resulting in approximately 400 × 40 constraints for the opti- grantee of the Bolyai J´anos Research Scholarship of the Hun-
mization problem. The exact number of variables in our sim- garian Academy of Sciences. The work has been also sup-
ulation (produced by the STL parser) was 10660 continuous ported by the UNKP-19-4-BME-29 New National Excellence
and 33110 integer variables. The solution of the problem on Program of the Ministry of Human Capacities.
an average consumer-grade laptop using two processor cores
was 217.7 seconds. 6. REFERENCES
To illustrate the detailed (second-phase) planning, we show [1] Gawrilow, E., Ko¨hler, E. and Mo¨hring, R. and Stenzel, B.
the planned routes and the generated input signals for only Dynamic Routing of Automated Guided Vehicles in
one agent corresponding to obstacle avoidance. The situa- Real-time (2008). In: Krebs HJ., Ja¨ger W. (eds)
tion is shown in Fig. 3. Here, we have the first-phase plan Mathematics – Key Technology for the Future. Springer,
generated for the agents, and we use the second phase com- Berlin, Heidelberg DOI: 10.1007/978-3-540-77203-3 12.
putation to calculate the detailed plan. The discretization
time for the second phase was t(s2) = t(s1)/10, with a horizon [2] B. Csutak, T. P´eni and G. Szederk´enyi. An optimization
of T = 50 steps. The rough plan is marked by the blue based algorithm for conflict-free navigation of autonomous
circles and consists of 5 intermediary points. The detailed guided vehicles In Pannonian Conference on Advances in
plan is marked by red stars. As it is visible in the figure, the Information Technology (2019), pp. 90-97.
agent remains in the prescribed proximity of the first-phase
plan. It must be noticed, that the agent correctly avoids [3] T. Nishi, M. Ando and M. Konishi. Distributed route
the obstacle’s corner, which was to be hit following directly planning for multiple mobile robots using an augmented
the first phase rough route. The input signals (acceleration Lagrangian decomposition and coordination technique In
commands) generated for the agent are displayed in Fig. 4 IEEE Transactions on Robotics, vol. 21, no. 6, pp.
1191-1200, Dec. 2005.
5. CONCLUSION
[4] E. S. Kim, S. Sadraddini, C. Belta, M. Arcak and S. A.
In this paper, we presented a possible way for describing Seshia. Dynamic contracts for distributed temporal logic
route planning problems as optimisation problems, using control of traffic networks In 2017 IEEE 56th Annual
the formalism offered by signal temporal logic. The plan- Conference on Decision and Control (CDC), Melbourne,
ning phase is divided into two parts: in the first phase, VIC, 2017, pp. 3640-3645.
we use a low-complexity model for creating a rough plan,
[5] Raman, V. and Donz´e, A. and Maasoumy, M. and Murray,
R. and Sangiovanni-Vincentelli, A. and A Seshia, S. (2014).
Model Predictive Control with Signal Temporal Logic
Specifications In 53rd IEEE Conference on Decision and
Control (2014): 81-87.
[6] A. Donz´e and V. Raman. BluSTL Controller Synthesis from
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 45
Koper, Slovenia, 10 October
The double-integrator model for the agents is used in the
and a target point, as well as a set of intermediary route 4
points Pi = {(xpi, ypi)|p = 1...T − 1} known from the pre-
vious phase. The planning is done using a rolling horizon 3 .
In the simplest case this means that at route point p, the 2
p + 2-th point is set as a target. We use a temporal logic
formula to ensure that the agent will be in the prescribed 1
proximity of the point p + 1, and planning is done on a hori-
zon of T2 = 2 · k. This can be easily extended to include 12345
more intermediary route points. This planning step is re-
peated when the agent reaches the route point p + 1. It can Figure 1: Distances kept by the agents during the
be shown, that by choosing this ∆ proximity correctly, we first and second phase planning
can guarantee, that no collision between the agents can oc-
cur. The concept of the proof is that if the distance threshold taking into consideration the obstacles and vehicle-vehicle
from the first phase is equal to the half of the distance, an interactions as well. The algorithm calculates a set of con-
agent can move in the rough plan in one step (δ = K/2), and secutive intermediary route points for each agent, ensuring
we restrict the agents to remain in the ∆ = δ/2 proximity conflict-free behavior provided that agents are in the given
of the given point for the respective time interval, then the proximity of the points for the respective time interval. In
agents are always located inside different non-overlapping the second phase, each agent computes its own path, con-
δ × δ-sized squares. The concept is illustrated in Figure 1. sidering the points and intervals given in the first phase.
Thus, vehicle-vehicle interactions need not to be checked on
4. ILLUSTRATIVE EXAMPLE the detailed planning level, only smooth maneuvering and
obstacle avoidance between the points are required.
In order to illustrate the concept, a case study containing
ten agents was carried out. As it is visible in Fig. 2, we Acknowledgements
have a 16 × 10 units floorplan, containing 7 obstacles that
must be avoided. The first-phase planning is running on a This work has been supported by the research program titled
40 step long horizon, which means at least 10 × 40 × 2 = 800 ”Exploring the Mathematical Foundations of Artificial In-
continuous variables (x and y directions for all agents and telligence” (2018-1.2.1-NKP-00008). The partial support of
all discrete time points). The number of temporal logic for- the projects GINOP-2.3.2-15-2016-00002 and EFOP-3.6.3-
mulas is 10 × 7 (obstacles) + 10 × 9/2 (collisions) = 115, VEKOP-16-2017-00002 is also acknowledged. T. P´eni is the
resulting in approximately 400 × 40 constraints for the opti- grantee of the Bolyai J´anos Research Scholarship of the Hun-
mization problem. The exact number of variables in our sim- garian Academy of Sciences. The work has been also sup-
ulation (produced by the STL parser) was 10660 continuous ported by the UNKP-19-4-BME-29 New National Excellence
and 33110 integer variables. The solution of the problem on Program of the Ministry of Human Capacities.
an average consumer-grade laptop using two processor cores
was 217.7 seconds. 6. REFERENCES
To illustrate the detailed (second-phase) planning, we show [1] Gawrilow, E., Ko¨hler, E. and Mo¨hring, R. and Stenzel, B.
the planned routes and the generated input signals for only Dynamic Routing of Automated Guided Vehicles in
one agent corresponding to obstacle avoidance. The situa- Real-time (2008). In: Krebs HJ., Ja¨ger W. (eds)
tion is shown in Fig. 3. Here, we have the first-phase plan Mathematics – Key Technology for the Future. Springer,
generated for the agents, and we use the second phase com- Berlin, Heidelberg DOI: 10.1007/978-3-540-77203-3 12.
putation to calculate the detailed plan. The discretization
time for the second phase was t(s2) = t(s1)/10, with a horizon [2] B. Csutak, T. P´eni and G. Szederk´enyi. An optimization
of T = 50 steps. The rough plan is marked by the blue based algorithm for conflict-free navigation of autonomous
circles and consists of 5 intermediary points. The detailed guided vehicles In Pannonian Conference on Advances in
plan is marked by red stars. As it is visible in the figure, the Information Technology (2019), pp. 90-97.
agent remains in the prescribed proximity of the first-phase
plan. It must be noticed, that the agent correctly avoids [3] T. Nishi, M. Ando and M. Konishi. Distributed route
the obstacle’s corner, which was to be hit following directly planning for multiple mobile robots using an augmented
the first phase rough route. The input signals (acceleration Lagrangian decomposition and coordination technique In
commands) generated for the agent are displayed in Fig. 4 IEEE Transactions on Robotics, vol. 21, no. 6, pp.
1191-1200, Dec. 2005.
5. CONCLUSION
[4] E. S. Kim, S. Sadraddini, C. Belta, M. Arcak and S. A.
In this paper, we presented a possible way for describing Seshia. Dynamic contracts for distributed temporal logic
route planning problems as optimisation problems, using control of traffic networks In 2017 IEEE 56th Annual
the formalism offered by signal temporal logic. The plan- Conference on Decision and Control (CDC), Melbourne,
ning phase is divided into two parts: in the first phase, VIC, 2017, pp. 3640-3645.
we use a low-complexity model for creating a rough plan,
[5] Raman, V. and Donz´e, A. and Maasoumy, M. and Murray,
R. and Sangiovanni-Vincentelli, A. and A Seshia, S. (2014).
Model Predictive Control with Signal Temporal Logic
Specifications In 53rd IEEE Conference on Decision and
Control (2014): 81-87.
[6] A. Donz´e and V. Raman. BluSTL Controller Synthesis from
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 45
Koper, Slovenia, 10 October
