Author name cluster

Vikraman Sathiyanarayanan

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.

3 papers

1 author row

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