Morris, Robert (NASA Ames Research Center) | Chang, Mai Lee (Johnson Space Center) | Archer, Ronald (Lockheed Martin) | Cross, Ernest V (Lockheed Martin) | Thompson, Shelby (Lockheed Martin) | Franke, Jerry (Lockheed Martin) | Garrett, Robert (Lockheed Martin) | Malik, Waqar (University of California-Santa Cruz Affiliated Research Center) | McGuire, Kerry (NASA Johnson Space Center) | Hemann, Garrett (Carnegie Mellon University)
We introduce an application of self-driving vehicle technology to the problem of towing aircraft at busy airports from gate to runway and runway to gate. Autonomous towing can be supervised by human ramp- or ATC controllers, pilots, or ground crew. The controllers provide route information to the tugs, assisted by an automated route planning system. The planning system and tower and ground controllers work in conjunction with the tugs to make tactical decisions during operations to ensure safe and effective taxiing in a highly dynamic environment. We argue here for the potential for significantly reducing fuel emissions, fuel costs, and community noise, while addressing the added complexity of air terminal operations by increasing efficiency and reducing human workload. This paper describes work-in-progress for developing concepts and capabilities for autonomous engines-off taxiing using towing vehicles.
We formalize the problem of multi-agent path finding with deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.
Hoenig, Wolfgang (University of Southern California) | Kumar, T. K. Satish (University of Southern California) | Cohen, Liron (University of Southern California) | Ma, Hang (University of Southern California) | Xu, Hong (University of Southern California) | Ayanian, Nora (University of Southern California) | Koenig, Sven (University of Southern California)
Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.
Schurr, Nathan (Aptima, Inc.) | Good, Richard (Aptima, Inc.) | Alexander, Amy (Aptima, Inc.) | Picciano, Paul (Aptima, Inc.) | Ganberg, Gabriel (Aptima, Inc.) | Therrien, Michael (Aptima, Inc.) | Beard, Bettina L. (NASA Ames Research Center) | Holbrook, Jon (San Jose State University Research Foundation)
To meet the growing demands of the National Airspace System (NAS) stakeholders and provide the level of service, safety and security needed to sustain future air transport, the Next Generation Air Transportation System (NextGen) concept calls for technologies and systems offering increasing support from automated systems that provide decision-aiding and optimization capabilities. This is an exciting application for some core aspects of Artificial Intelligence research since the automation must be designed to enable the human operators to access and process a myriad of information sources, understand heightened system complexity, and maximize capacity, throughput and fuel savings in the NAS.. This paper introduces an emerging application of techniques from mixed initiative (adjustable autonomy), multi-agent systems, and task scheduling techniques to the air traffic control domain. Consequently, we have created a testbed for investigating the critical challenges in supporting the early design of systems that allow for optimal, context-sensitive function (role) allocation between air traffic controller and automated agents. A pilot study has been conducted with the testbed and preliminary results show a marked qualitative improvement in using dynamic function allocation optimization versus static function allocation.
This paper summarizes the evolution of our research on the Cooperative Intelligent Real-Time Control Architecture (CIRCA), one of the first AI architectures designed specifically for hard-real-time environments and architecturally-enforced performance guarantees. Beginning with the objective of providing reliable real-time execution of automatically-generated plans, CIRCA research progressed to define a rigorous link between planning models, execution semantics, and performance guarantees. Formal verification techniques and automatic abstraction methods were then incorporated to improve the rigor and performance of the planning system. Multi-agent negotiation and coordination capabilities were developed to demonstrate performance guarantees spanning distributed CIRCA agents. As the limitations of CIRCA's fully-guaranteed semantics became clear, the research grew to include probabilistic versions of the problem and new solution methods. Versions of CIRCA are capable of reasoning about durative concurrent actions, exogenous events and adversaries, nondeterministic actions, and probabilistic actions and events.