Distributed safe planning for satisfying minimal temporal relaxations of TWTL specifications

Ryan Peterson; Ali Tevfik Buyukkocak; Derya Aksaray; Yasin Yazıcıoğlu

doi:10.1016/j.robot.2021.103801

Distributed safe planning for satisfying minimal temporal relaxations of TWTL specifications

Ryan Peterson, Ali Tevfik Buyukkocak, Derya Aksaray, Yasin Yazıcıoğlu

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

We investigate a multi-agent planning problem, where each agent aims to achieve an individual task while avoiding collisions with other agents. Each agent's task is expressed as a Time-Window Temporal Logic (TWTL) specification defined over a discretized environment. We propose a distributed receding horizon algorithm for online planning of agent trajectories. We show that under mild assumptions on the environment, the resulting trajectories are always safe (collision-free) and lead to the satisfaction of the TWTL specifications or a finite temporal relaxation. Accordingly, each agent is guaranteed to safely achieve its task, possibly with some minimal finite delay. Performance of the proposed algorithm is demonstrated via numerical simulations and experiments with quadrotors.

Original language	English (US)
Article number	103801
Journal	Robotics and Autonomous Systems
Volume	142
DOIs	https://doi.org/10.1016/j.robot.2021.103801
State	Published - Aug 1 2021

Bibliographical note

Funding Information:
Some preliminary results of this work were presented at the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Peterson et al., 2020). This work was partially supported at the University of Minnesota, United States by Honeywell Aerospace and MnDRIVE, University of Minnesota, United States .

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

Collision avoidance
Distributed planning
Formal methods
Multi-agent systems

Publisher link

10.1016/j.robot.2021.103801

Find It

Find It at U of M Libraries

Cite this

@article{051a82ab0adb42ef8a43b2a777619b90,

title = "Distributed safe planning for satisfying minimal temporal relaxations of TWTL specifications",

abstract = "We investigate a multi-agent planning problem, where each agent aims to achieve an individual task while avoiding collisions with other agents. Each agent's task is expressed as a Time-Window Temporal Logic (TWTL) specification defined over a discretized environment. We propose a distributed receding horizon algorithm for online planning of agent trajectories. We show that under mild assumptions on the environment, the resulting trajectories are always safe (collision-free) and lead to the satisfaction of the TWTL specifications or a finite temporal relaxation. Accordingly, each agent is guaranteed to safely achieve its task, possibly with some minimal finite delay. Performance of the proposed algorithm is demonstrated via numerical simulations and experiments with quadrotors.",

keywords = "Collision avoidance, Distributed planning, Formal methods, Multi-agent systems",

author = "Ryan Peterson and Buyukkocak, {Ali Tevfik} and Derya Aksaray and Yasin Yazıcıoğlu",

note = "Funding Information: Some preliminary results of this work were presented at the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Peterson et al., 2020). This work was partially supported at the University of Minnesota, United States by Honeywell Aerospace and MnDRIVE, University of Minnesota, United States . Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = aug,

day = "1",

doi = "10.1016/j.robot.2021.103801",

language = "English (US)",

volume = "142",

journal = "Robotics and Autonomous Systems",

issn = "0921-8890",

publisher = "Elsevier",

}

TY - JOUR

T1 - Distributed safe planning for satisfying minimal temporal relaxations of TWTL specifications

AU - Peterson, Ryan

AU - Buyukkocak, Ali Tevfik

AU - Aksaray, Derya

AU - Yazıcıoğlu, Yasin

N1 - Funding Information: Some preliminary results of this work were presented at the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Peterson et al., 2020). This work was partially supported at the University of Minnesota, United States by Honeywell Aerospace and MnDRIVE, University of Minnesota, United States . Publisher Copyright: © 2021 Elsevier B.V.

PY - 2021/8/1

Y1 - 2021/8/1

N2 - We investigate a multi-agent planning problem, where each agent aims to achieve an individual task while avoiding collisions with other agents. Each agent's task is expressed as a Time-Window Temporal Logic (TWTL) specification defined over a discretized environment. We propose a distributed receding horizon algorithm for online planning of agent trajectories. We show that under mild assumptions on the environment, the resulting trajectories are always safe (collision-free) and lead to the satisfaction of the TWTL specifications or a finite temporal relaxation. Accordingly, each agent is guaranteed to safely achieve its task, possibly with some minimal finite delay. Performance of the proposed algorithm is demonstrated via numerical simulations and experiments with quadrotors.

AB - We investigate a multi-agent planning problem, where each agent aims to achieve an individual task while avoiding collisions with other agents. Each agent's task is expressed as a Time-Window Temporal Logic (TWTL) specification defined over a discretized environment. We propose a distributed receding horizon algorithm for online planning of agent trajectories. We show that under mild assumptions on the environment, the resulting trajectories are always safe (collision-free) and lead to the satisfaction of the TWTL specifications or a finite temporal relaxation. Accordingly, each agent is guaranteed to safely achieve its task, possibly with some minimal finite delay. Performance of the proposed algorithm is demonstrated via numerical simulations and experiments with quadrotors.

KW - Collision avoidance

KW - Distributed planning

KW - Formal methods

KW - Multi-agent systems

UR - http://www.scopus.com/inward/record.url?scp=85107625617&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85107625617&partnerID=8YFLogxK

U2 - 10.1016/j.robot.2021.103801

DO - 10.1016/j.robot.2021.103801

M3 - Article

AN - SCOPUS:85107625617

SN - 0921-8890

VL - 142

JO - Robotics and Autonomous Systems

JF - Robotics and Autonomous Systems

M1 - 103801

ER -

Distributed safe planning for satisfying minimal temporal relaxations of TWTL specifications

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this