UAS Batch Path Planning With a Space-Time Graph

Unmanned Aircraft Systems (UAS) provide the platform of many applications such as efficient package delivery, monitoring, surveillance, search and rescue, and more. As the density of UAS deployed in urban areas for delivery and monitoring operations is expected to increase in the near future, it bec...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Andrew Steinberg, Mihaela Cardei, Ionut Cardei
Formato:	article
Lenguaje:	EN
Publicado:	IEEE 2021
Materias:	UAS path planning space-time graph UAS traffic management Transportation engineering TA1001-1280 Transportation and communications HE1-9990
Acceso en línea:	https://doaj.org/article/7239f6bb644f416ebf26d7f8a06c831e
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:7239f6bb644f416ebf26d7f8a06c831e
record_format	dspace
spelling	oai:doaj.org-article:7239f6bb644f416ebf26d7f8a06c831e2021-11-19T00:07:18ZUAS Batch Path Planning With a Space-Time Graph2687-781310.1109/OJITS.2021.3070415https://doaj.org/article/7239f6bb644f416ebf26d7f8a06c831e2021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9393475/https://doaj.org/toc/2687-7813Unmanned Aircraft Systems (UAS) provide the platform of many applications such as efficient package delivery, monitoring, surveillance, search and rescue, and more. As the density of UAS deployed in urban areas for delivery and monitoring operations is expected to increase in the near future, it becomes critical to design an efficient collision-free UAS path planning system to be used by a centralized traffic manager. In this article we propose an on-demand, scalable, collision-free trajectory planning mechanism that processes routing requests in batches, with the objective of improving the ratio of successfully admitted requests. The planner transforms the input map to a unit graph discretized on the safety distance and computes trajectories using search in the derived space-time graph. The planner generates trajectories that are by design conflict-free and deadlock-free. The performance of our algorithm is analyzed with simulations. We measure admission ratio, the delay overhead vs. optimal path delay, the algorithm running time, and we compare results with prior work. The proposed batch planner yields better admission ratio and delay overhead in low and medium density scenarios. In all scenarios it has a running time that is 4-7 times shorter, showing its scalability in practical situations.Andrew SteinbergMihaela CardeiIonut CardeiIEEEarticleUAS path planningspace-time graphUAS traffic managementTransportation engineeringTA1001-1280Transportation and communicationsHE1-9990ENIEEE Open Journal of Intelligent Transportation Systems, Vol 2, Pp 60-72 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	UAS path planning space-time graph UAS traffic management Transportation engineering TA1001-1280 Transportation and communications HE1-9990
spellingShingle	UAS path planning space-time graph UAS traffic management Transportation engineering TA1001-1280 Transportation and communications HE1-9990 Andrew Steinberg Mihaela Cardei Ionut Cardei UAS Batch Path Planning With a Space-Time Graph
description	Unmanned Aircraft Systems (UAS) provide the platform of many applications such as efficient package delivery, monitoring, surveillance, search and rescue, and more. As the density of UAS deployed in urban areas for delivery and monitoring operations is expected to increase in the near future, it becomes critical to design an efficient collision-free UAS path planning system to be used by a centralized traffic manager. In this article we propose an on-demand, scalable, collision-free trajectory planning mechanism that processes routing requests in batches, with the objective of improving the ratio of successfully admitted requests. The planner transforms the input map to a unit graph discretized on the safety distance and computes trajectories using search in the derived space-time graph. The planner generates trajectories that are by design conflict-free and deadlock-free. The performance of our algorithm is analyzed with simulations. We measure admission ratio, the delay overhead vs. optimal path delay, the algorithm running time, and we compare results with prior work. The proposed batch planner yields better admission ratio and delay overhead in low and medium density scenarios. In all scenarios it has a running time that is 4-7 times shorter, showing its scalability in practical situations.
format	article
author	Andrew Steinberg Mihaela Cardei Ionut Cardei
author_facet	Andrew Steinberg Mihaela Cardei Ionut Cardei
author_sort	Andrew Steinberg
title	UAS Batch Path Planning With a Space-Time Graph
title_short	UAS Batch Path Planning With a Space-Time Graph
title_full	UAS Batch Path Planning With a Space-Time Graph
title_fullStr	UAS Batch Path Planning With a Space-Time Graph
title_full_unstemmed	UAS Batch Path Planning With a Space-Time Graph
title_sort	uas batch path planning with a space-time graph
publisher	IEEE
publishDate	2021
url	https://doaj.org/article/7239f6bb644f416ebf26d7f8a06c831e
work_keys_str_mv	AT andrewsteinberg uasbatchpathplanningwithaspacetimegraph AT mihaelacardei uasbatchpathplanningwithaspacetimegraph AT ionutcardei uasbatchpathplanningwithaspacetimegraph
_version_	1718420615454523392

UAS Batch Path Planning With a Space-Time Graph

Ejemplares similares