Page 43 - 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. 43
rarchical Routing Algorithm for Industrial Mobile
Robots by Signal Temporal Logic Specifications
[Extended Abstract]
Balázs Csutak Tamás Péni Gábor Szederkényi
Faculty of Information Systems and Control Faculty of Information
Technology and Bionics, Laboratory, Institute for Technology and Bionics,
Pázmány Péter Catholic Computer Science and Pázmány Péter Catholic
University Control University
H-1083 Práter u. 50/a, H-1111 Kende u. 13-17., H-1083 Práter u. 50/a,
Budapest, Hungary Budapest, Hungary Budapest, Hungary
csutak.balazs@hallgato. peni.tamas@sztaki.mta.hu szederkenyi@itk.ppke.hu
ppke.hu
ABSTRACT space (e.g. in an industrial plant), assuming a microscopic
routing environment (i.e., the size of the vehicles is not neg-
A two-level route planning algorithm based on model predic- ligible compared to the available space). This environment
tive control (MPC) is proposed in this paper for industrial can be modeled as a directed graph, with only one agent
mobile robots, executing tasks in an environment specified allowed at a time in a given node or edge [1], which is suit-
using the methodology of signal temporal logic (STL). STL able for a physically large setting, but might prove to be
is applied to describe various conditions like collision-free ineffective in a more crowded location. As another possible
and deadlock-free operation, followed by the transforma- approach, the plant can be modeled as a coordinates sys-
tion of the formulas into a mixed integer linear program- tem, in which agents can move freely with the exception of
ming (MILP) problem, solved using dedicated software. To a number of obstacles or restricted zones.
achieve real-time operation, the route planning is divided
into two distinct phases using different underlying vehicle Some of the solutions concentrate on giving suboptimal but
models. The correctness of the approach is guaranteed by real-time solution for the problem, using greedy iterative al-
the applied formal design method. gorithms or heuristics. In the simplest case, the route plan-
ning of the agents is carried out in a completely independent
Categories and Subject Descriptors manner: knowing the location of the obstacles, each agent
computes a path locally, and avoids collision with other vehi-
[Embedded and cyber-physical systems]: Robotics— cles in real-time. This approach however is neither optimal
Robotic control ; [Applied computing]: Physical sciences regarding the completion time of the movements, nor has
and engineering—Engineering any guarantee to prevent situations like a deadlock forma-
tion. More complex solutions feature distributed calcula-
Keywords tion, but with a centrally accessible resource (like already
planned paths of the other vehicles) [1, 2].
mobile robots, route planning, signal temporal logic, opti-
mization It is also possible to model route planning tasks as opti-
mization problems [3]. These algorithms are indeed capable
1. INTRODUCTION of giving the truly optimal solution regarding completion
time, guarantee the collision-free and deadlock-free opera-
Optimal route planning based on transport demands is an tion on the price of high computational complexity which
intensively investigated topic in engineering fields. Depend- might hamper real-time application.
ing on the applied model and assumptions, the computa-
tional complexity of such tasks and the effectiveness of the Linear Temporal Logic (LTL) is a formalism originally de-
solution moves on a wide scale. veloped for the formal design and verification of computer
programs. In essence, LTL extends the set of operators fa-
The problem itself generally consists of numerous autonomous miliar from Boolean logic with tools to describe time depen-
guided vehicles (AGV) moving along given routes in a closed dencies between the statements (such as ’always’, ’never’,
’eventually’, ’next step’, etc.). Signal Temporal Logic (STL)
further extends the possibilities offered by LTL by introduc-
ing quantitative operators regarding time in LTL formulas.
STL has been successfully used for describing traffic-related
systems, due to its ability to express complex rule sets or
complicated time dependencies [4, 7, 8].
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.43-47 43
Koper, Slovenia, 10 October
Robots by Signal Temporal Logic Specifications
[Extended Abstract]
Balázs Csutak Tamás Péni Gábor Szederkényi
Faculty of Information Systems and Control Faculty of Information
Technology and Bionics, Laboratory, Institute for Technology and Bionics,
Pázmány Péter Catholic Computer Science and Pázmány Péter Catholic
University Control University
H-1083 Práter u. 50/a, H-1111 Kende u. 13-17., H-1083 Práter u. 50/a,
Budapest, Hungary Budapest, Hungary Budapest, Hungary
csutak.balazs@hallgato. peni.tamas@sztaki.mta.hu szederkenyi@itk.ppke.hu
ppke.hu
ABSTRACT space (e.g. in an industrial plant), assuming a microscopic
routing environment (i.e., the size of the vehicles is not neg-
A two-level route planning algorithm based on model predic- ligible compared to the available space). This environment
tive control (MPC) is proposed in this paper for industrial can be modeled as a directed graph, with only one agent
mobile robots, executing tasks in an environment specified allowed at a time in a given node or edge [1], which is suit-
using the methodology of signal temporal logic (STL). STL able for a physically large setting, but might prove to be
is applied to describe various conditions like collision-free ineffective in a more crowded location. As another possible
and deadlock-free operation, followed by the transforma- approach, the plant can be modeled as a coordinates sys-
tion of the formulas into a mixed integer linear program- tem, in which agents can move freely with the exception of
ming (MILP) problem, solved using dedicated software. To a number of obstacles or restricted zones.
achieve real-time operation, the route planning is divided
into two distinct phases using different underlying vehicle Some of the solutions concentrate on giving suboptimal but
models. The correctness of the approach is guaranteed by real-time solution for the problem, using greedy iterative al-
the applied formal design method. gorithms or heuristics. In the simplest case, the route plan-
ning of the agents is carried out in a completely independent
Categories and Subject Descriptors manner: knowing the location of the obstacles, each agent
computes a path locally, and avoids collision with other vehi-
[Embedded and cyber-physical systems]: Robotics— cles in real-time. This approach however is neither optimal
Robotic control ; [Applied computing]: Physical sciences regarding the completion time of the movements, nor has
and engineering—Engineering any guarantee to prevent situations like a deadlock forma-
tion. More complex solutions feature distributed calcula-
Keywords tion, but with a centrally accessible resource (like already
planned paths of the other vehicles) [1, 2].
mobile robots, route planning, signal temporal logic, opti-
mization It is also possible to model route planning tasks as opti-
mization problems [3]. These algorithms are indeed capable
1. INTRODUCTION of giving the truly optimal solution regarding completion
time, guarantee the collision-free and deadlock-free opera-
Optimal route planning based on transport demands is an tion on the price of high computational complexity which
intensively investigated topic in engineering fields. Depend- might hamper real-time application.
ing on the applied model and assumptions, the computa-
tional complexity of such tasks and the effectiveness of the Linear Temporal Logic (LTL) is a formalism originally de-
solution moves on a wide scale. veloped for the formal design and verification of computer
programs. In essence, LTL extends the set of operators fa-
The problem itself generally consists of numerous autonomous miliar from Boolean logic with tools to describe time depen-
guided vehicles (AGV) moving along given routes in a closed dencies between the statements (such as ’always’, ’never’,
’eventually’, ’next step’, etc.). Signal Temporal Logic (STL)
further extends the possibilities offered by LTL by introduc-
ing quantitative operators regarding time in LTL formulas.
STL has been successfully used for describing traffic-related
systems, due to its ability to express complex rule sets or
complicated time dependencies [4, 7, 8].
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.43-47 43
Koper, Slovenia, 10 October
