Thayne T. Walker

Thayne T Walker, Nathan R Sturtevant

Conflict-Based Search (CBS) algorithm for the multi-agent pathfinding (MAPF) problem is that it is incomplete for problems which have no solution; if no mitigating procedure is run in parallel, CBS will run forever when given an unsolvable problem instance. In this work, we introduce Temporally-Relative Duplicate Pruning (TRDP), a technique for duplicate detection and removal in both classic and continuous-time MAPF domains. TRDP is a simple procedure which closes the long-standing theoretic loophole of incompleteness for CBS by detecting and avoiding the expansion of duplicate states. TRDP is shown both theoretically and empirically to ensure termination without a significant impact on runtime in the majority of problem instances. In certain cases, TRDP is shown to increase performance significantly

Thayne T. Walker, Nathan R. Sturtevant, Ariel Felner

While the study of unit-cost Multi-Agent Pathfinding (MAPF) problems has been popular, many real-world problems require continuous time and costs due to various movement models. In this context, this paper studies symmetry-breaking enhancements for Continuous-Time Conflict-Based Search (CCBS), a solver for continuous-time MAPF. Resolving conflict symmetries in MAPF can require an exponential amount of work. We adapt known enhancements from unit-cost domains for CCBS: bypassing, which resolves cost symmetries and biclique constraints which resolve spatial conflict symmetries. We formulate a novel combination of biclique constraints with disjoint splitting for spatial conflict symmetries. Finally, we show empirically that these enhancements yield a statistically significant performance improvement versus previous state of the art, solving problems for up to 10% or 20% more agents in the same amount of time on dense graphs.

Wanlin Xie, Jaime Ide, Daniel Izadi et al.

Multi-object tracking (MOT) is a crucial component of situational awareness in military defense applications. With the growing use of unmanned aerial systems (UASs), MOT methods for aerial surveillance is in high demand. Application of MOT in UAS presents specific challenges such as moving sensor, changing zoom levels, dynamic background, illumination changes, obscurations and small objects. In this work, we present a robust object tracking architecture aimed to accommodate for the noise in real-time situations. We propose a kinematic prediction model, called Deep Extended Kalman Filter (DeepEKF), in which a sequence-to-sequence architecture is used to predict entity trajectories in latent space. DeepEKF utilizes a learned image embedding along with an attention mechanism trained to weight the importance of areas in an image to predict future states. For the visual scoring, we experiment with different similarity measures to calculate distance based on entity appearances, including a convolutional neural network (CNN) encoder, pre-trained using Siamese networks. In initial evaluation experiments, we show that our method, combining scoring structure of the kinematic and visual models within a MHT framework, has improved performance especially in edge cases where entity motion is unpredictable, or the data presents frames with significant gaps.

Adrian P. Pope, Jaime S. Ide, Daria Micovic et al.

Artificial Intelligence (AI) is becoming a critical component in the defense industry, as recently demonstrated by DARPA`s AlphaDogfight Trials (ADT). ADT sought to vet the feasibility of AI algorithms capable of piloting an F-16 in simulated air-to-air combat. As a participant in ADT, Lockheed Martin`s (LM) approach combines a hierarchical architecture with maximum-entropy reinforcement learning (RL), integrates expert knowledge through reward shaping, and supports modularity of policies. This approach achieved a $2^{nd}$ place finish in the final ADT event (among eight total competitors) and defeated a graduate of the US Air Force's (USAF) F-16 Weapons Instructor Course in match play.

Thayne T. Walker, Nathan R. Sturtevant

Recent work on the multi-agent pathfinding problem (MAPF) has begun to study agents with motion that is more complex, for example, with non-unit action durations and kinematic constraints. An important aspect of MAPF is collision detection. Many collision detection approaches exist, but often suffer from issues such as high computational cost or causing false negative or false positive detections. In practice, these issues can result in problems that range from inefficiency and annoyance to catastrophic. The main contribution of this technical report is to provide a high-level overview of major categories of collision detection, along with methods of collision detection and anticipatory collision avoidance for agents that are both computationally efficient and highly accurate.

Roni Stern, Nathan Sturtevant, Ariel Felner et al.

The MAPF problem is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses and autonomous vehicles. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers make different assumptions, e.g., whether agents can traverse the same road at the same time, and have different objective functions, e.g., minimize makespan or sum of agents' actions costs. These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult to establish appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. This paper aims to fill this gap and support researchers and practitioners by providing a unifying terminology for describing common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks. In particular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms.