7 September 2020 in IEEE Transactions on Intelligent Transportation Systems
The development of a real-world Unmanned Aircraft System (UAS) Traffic Management (UTM) system to ensure the safe integration of Unmanned Aerial Vehicles (UAVs) in low altitude airspace, has recently generated novel research challenges. A key problem is the development of Pre-Flight Conflict Detection and Resolution (CDR) methods that provide collision-free flight paths to all UAVs before their takeoff. Such problem can be represented as a Multi-Agent Path Finding (MAPF) problem. Currently, most MAPF methods assume that the UTM system is a centralized entity in charge of CDR. However, recent discussions on UTM suggest that such centralized control might not be practical or desirable. Therefore, we explore Pre-Flight CDR methods where independent UAS Service Providers (UASSPs) with their own interests, communicate with each other to resolve conflicts among their UAV operations--without centralized UTM directives. We propose a novel MAPF model that supports the decentralized resolution of conflicts, whereby different `agents', here UASSPs, manage their UAV operations. We present two approaches: (1) a prioritization approach and (2) a simple yet practical pairwise negotiation approach where UASSPs agents determine an agreement to solve conflicts between their UAV operations. We evaluate the performance of our proposed approaches with simulation scenarios based on a consultancy study of predicted UAV traffic for delivery services in Sendai, Japan, 2030. We demonstrate that our negotiation approach improves the ``fairness'' between UASSPs, i.e. the distribution of costs between UASSPs in terms of total delays and rejected operations due to replanning is more balanced when compared to the prioritization approach.
23 December 2018 in IEEE Transactions on Vehicular Technology
In future unmanned aerial vehicle (UAV)-based services, UAV fleets will be managed by several independent flight operation service providers in shared low-altitude airspace. Therefore, conflict detection and resolution (CDR) methods that can solve conflicts-possible collisions between UAVs of different service providers-are a key element of the unmanned aircraft system traffic management system. As our CDR method, we introduce an adaptation of ORCA, which is a state-of-the-art collision avoidance algorithm hitherto mainly used in a limited theoretical scope, to realistic UAV operations. Our approach, called adapted ORCA, addresses practical considerations that are inherent to the deployment of UAVs in shared airspace, such as navigation inaccuracies, communication overhead, and flight phases. We validate our approach through simulations. First, by empirically tuning the ORCA parameters look-ahead time window and deconfliction distance, we are able to minimize the ORCA generated deviations from the nominal flight path. Second, by simulating realistic UAV traffic for delivery, we can determine a value for separation distance between UAVs that uses airspace efficiently.
21 November 2019 in IEEE Access
The increasing demand for services performed by Unmanned Aerial Vehicles (UAVs) requires the simulation of Unmanned Aircraft System Traffic Management (UTM) systems. In particular, Pre-Flight Conflict Detection and Resolution (CDR) methods need to scale to future demand levels and generate conflict-free paths for a potentially large number of UAVs before actual takeoff. However, few studies have examined realistic scenarios and the requirements for the UTM system. In this paper, we focus on the Sendai 2030 model case, a realistic projection of UAV usage for deliveries in one area in Japan. This model case considers up to 21,000 requests for Unmanned Aircraft Systems (UAS) operations over a 13 hour service time, and thus poses a challenge for the Pre-Flight CDR methods. Therefore, we propose an airspace reservation method based on 4DT (3D plus time Trajectories) and map the Pre-Flight CDR problem to a Multi-Agent Path Finding (MAPF) problem. We study first-come first-served (FCFS) and “batch” processing of UAS operation requests, and compare the throughput of those methods. We analyze the air traffic topology of deliveries by UAVs, and discuss several metrics to better understand the complexity of air traffic in the Sendai model case.
6 September 2024 in IEEE Robotics and Automation Letters
This letter addresses the joint task allocation and path planning problem, whereby a fleet of vehicles must be optimally assigned to service multiple given tasks while their planned paths must be collision-free. Such a problem composed of two tightly coupled optimization problems has a high complexity with the number of tasks and the number of vehicles, thus optimal solvers do not scale to large size instances. Therefore, we propose a novel method to solve this problem, HTAPPS, which introduces a hierarchical resolution framework. Our proposed approach decomposes a given instance into three levels of abstractions and associated amount of details that progressively filter the search space. This allows us to reduce the computational effort required when performing task allocation and multi-agent path planning jointly. We perform simulations on automated warehouse scenarios, and compare our approach to baseline solvers. The obtained results show that our proposed approach is able to solve large size instances within a limited time.
23 December 2022 in Autonomous Agents and Multi-Agent Systems