Author name cluster

Eric Ewing

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AAMAS Conference 2025 Conference Paper

Empirical Hardness in Multi-Agent Pathfinding: Research Challenges and Opportunities

Jingyao Ren
Eric Ewing
T. K. Satish Kumar
Sven Koenig
Nora Ayanian

Multi-agent pathfinding (MAPF) is the problem of finding collisionfree paths for a team of agents on a map. Although MAPF is NPhard, the hardness of solving individual instances varies significantly, revealing a gap between theoretical complexity and actual hardness. This paper outlines three key research challenges in MAPF empirical hardness to understand such phenomena. The first challenge, known as algorithm selection, is determining the bestperforming algorithms for a given instance. The second challenge is understanding the key instance features that affect MAPF empirical hardness, such as structural properties like phase transition and backbone/backdoor. The third challenge is how to leverage our knowledge of MAPF empirical hardness to effectively generate hard MAPF instances or diverse benchmark datasets. This work establishes a foundation for future empirical hardness research and encourages deeper investigation into these promising and underexplored areas.

PDF

ICAPS Conference 2024 Conference Paper

Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem

Jingyao Ren
Eric Ewing
T. K. Satish Kumar
Sven Koenig
Nora Ayanian

We present an empirical study of the relationship between map connectivity and the empirical hardness of the multi-agent pathfinding (MAPF) problem. By analyzing the second smallest eigenvalue (commonly known as lambda2) of the normalized Laplacian matrix of different maps, our initial study indicates that maps with smaller lambda2 tend to create more challenging instances when agents are generated uniformly randomly. Additionally, we introduce a map generator based on Quality Diversity (QD) that is capable of producing maps with specified lambda2 ranges, offering a possible way for generating challenging MAPF instances. Despite the absence of a strict monotonic correlation with lambda2 and the empirical hardness of MAPF, this study serves as a valuable initial investigation for gaining a deeper understanding of what makes a MAPF instance hard to solve.

Details

AAMAS Conference 2022 Conference Paper

Betweenness Centrality in Multi-Agent Path Finding

Eric Ewing
Jingyao Ren
Dhvani Kansara
Vikraman Sathiyanarayanan
Nora Ayanian

Multi-Agent Path Finding (MAPF) is a well studied problem with many existing optimal algorithms capable of solving a wide variety of instances, each with its own strengths and weaknesses. While for some instances the fastest algorithm can be easily determined, not enough is known about their performance to predict the fastest algorithm for every MAPF instance, or what makes some instances more difficult than others. There is no clear answer for which features dominate the hardness of MAPF instances. In this work, we study how betweenness centrality affects the empirical difficulty of MAPF instances. To that end, we benchmark the largest and most complete optimal MAPF algorithm portfolio to date. We analyze the algorithms’ performance independently and as part of the portfolio, and discuss how betweenness centrality can be used to improve estimations of algorithm performance on a given instance of MAPF.

PDF

AAAI Conference 2021 Short Paper

Automatic Optimal Multi-Agent Path Finding Algorithm Selector (Student Abstract)

Jingyao Ren
Vikraman Sathiyanarayanan
Eric Ewing
Baskin Senbaslar
Nora Ayanian

Solving Multi-Agent Path Finding (MAPF) problems optimally is known to be NP-Hard for both make-span and total arrival time minimization. Many algorithms have been developed to solve MAPF problems optimally and they all have different strengths and weaknesses. There is no dominating MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. Therefore, there is a need for developing an automatic algorithm selector that suggests the best optimal algorithm to use given a MAPF problem instance. We propose a model based on convolutions and inception modules by treating the input MAPF instance as an image. We further show that techniques such as single-agent shortest path annotation and graph embedding are very effective for improving training quality. We evaluate our model and show that it outperforms all individual algorithms in its portfolio, as well as an existing state-of-theart MAPF algorithm selector.

PDF Details

AAMAS Conference 2021 Conference Paper

MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings

Jingyao Ren
Vikraman Sathiyanarayanan
Eric Ewing
Baskin Senbaslar
Nora Ayanian

Solving the Multi-Agent Path Finding (MAPF) problem optimally is known to be NP-Hard for both make-span and total arrival time minimization. While many algorithms have been developed to solve MAPF problems, there is no dominating optimal MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. In this work, we develop the deep convolutional network MAPFAST (Multi-Agent Path Finding Algorithm SelecTor), which takes a MAPF problem instance and attempts to select the fastest algorithm to use from a portfolio of algorithms. We improve the performance of our model by including single-agent shortest paths in the instance embedding given to our model and by utilizing supplemental loss functions in addition to a classification loss. We evaluate our model on a large and diverse dataset of MAPF instances, showing that it outperforms all individual algorithms in its portfolio as well as the state-of-the-art optimal MAPF algorithm selector. We also provide an analysis of algorithm behavior in our dataset to gain a deeper understanding of optimal MAPF algorithms’ strengths and weaknesses to help other researchers leverage different heuristics in algorithm designs.

PDF

AAAI Conference 2020 Conference Paper

End-to-End Game-Focused Learning of Adversary Behavior in Security Games

Andrew Perrault
Bryan Wilder
Eric Ewing
Aditya Mate
Bistra Dilkina
Milind Tambe

Stackelberg security games are a critical tool for maximizing the utility of limited defense resources to protect important targets from an intelligent adversary. Motivated by green security, where the defender may only observe an adversary’s response to defense on a limited set of targets, we study the problem of learning a defense that generalizes well to a new set of targets with novel feature values and combinations. Traditionally, this problem has been addressed via a two-stage approach where an adversary model is trained to maximize predictive accuracy without considering the defender’s optimization problem. We develop an end-to-end game-focused approach, where the adversary model is trained to maximize a surrogate for the defender’s expected utility. We show both in theory and experimental results that our game-focused approach achieves higher defender expected utility than the two-stage alternative when there is limited data.

PDF Details

NeurIPS Conference 2019 Conference Paper

End to end learning and optimization on graphs

Bryan Wilder
Eric Ewing
Bistra Dilkina
Milind Tambe

Real-world applications often combine learning and optimization problems on graphs. For instance, our objective may be to cluster the graph in order to detect meaningful communities (or solve other common graph optimization problems such as facility location, maxcut, and so on). However, graphs or related attributes are often only partially observed, introducing learning problems such as link prediction which must be solved prior to optimization. Standard approaches treat learning and optimization entirely separately, while recent machine learning work aims to predict the optimal solution directly from the inputs. Here, we propose an alternative decision-focused learning approach that integrates a differentiable proxy for common graph optimization problems as a layer in learned systems. The main idea is to learn a representation that maps the original optimization problem onto a simpler proxy problem that can be efficiently differentiated through. Experimental results show that our ClusterNet system outperforms both pure end-to-end approaches (that directly predict the optimal solution) and standard approaches that entirely separate learning and optimization. Code for our system is available at https: //github. com/bwilder0/clusternet.

PDF Details