More Like this

1. Betweenness Centrality in Multi-Agent Path Finding

   Ewing, Eric; Ren, Jingyao; Kansara, Dhvani; Sathiyanarayanan, Vikraman; Ayanian, Nora (May 2022, AAMAS Conference proceedings)

   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. 

   more » « less
2. MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings

   Ren, Jingyao; Sathiyanarayanan, Vikraman; Ewing, Eric; Senbaslar, Baskin; Ayanian, Nora (May 2021, Autonomous agents and multiagent systems)

   null (Ed.)

   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 di- verse 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. 

   more » « less
3. Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter

   https://doi.org/10.1145/3563393  

   Abboud, Amir; Grandoni, Fabrizio; Vassilevska_Williams, Virginia (January 2023, ACM Transactions on Algorithms)

   Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks, and so forth. Differentcentralitymeasures have been proposed to capture the notion of node importance. For example, thecenterof a graph is a node that minimizes the maximum distance to any other node (the latter distance is theradiusof the graph). Themedianof a graph is a node that minimizes the sum of the distances to all other nodes. Informally, thebetweenness centralityof a nodewmeasures the fraction of shortest paths that havewas an intermediate node. Finally, thereach centralityof a nodewis the smallest distancersuch that anys-tshortest path passing throughwhas eithersortin the ball of radiusraroundw. The fastest known algorithms to compute the center and the median of a graph and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the numbernof nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e., algorithms with running time Õ(n^3-δ) for some constant δ > 0.¹ We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median, and Betweenness Centrality areequivalent under subcubic reductionsto APSP, i.e., that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any finite factor. Thus, the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP required essentially cubic time. On the positive side, our reductions for Reach Centrality imply an improved Õ(Mn^ω)-time algorithm for this problem in case of non-negative integer weights upper bounded byM, where ω is a fast matrix multiplication exponent. 

   more » « less
4. From Multi-Agent Pathfinding to 3D Pipe Routing

   Belov, G.; Du, W.; Garcia de al Banda, M.; Harabor, D.; Koenig, S.; and Wei, X. (January 2020, Symposium on Combinatorial Search (SoCS))

   The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal locations in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance for automated warehouses (such as those operated by Amazon) and other important application areas. In this paper, we demonstrate that some recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on real-world PR instances. This opens up a new direction of industrial relevance for the MAPF research community. 

   more » « less
5. Generalization in portfolio-based algorithm selection

   Balcan, M.-F.; Sandholm, T.; Vitercik, E. (January 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   Portfolio-based algorithm selection has seen tremendous practical success over the past two decades. This algorithm configuration procedure works by first selecting a portfolio of diverse algorithm parameter settings, and then, on a given problem instance, using an algorithm selector to choose a parameter setting from the portfolio with strong predicted performance. Oftentimes, both the portfolio and the algorithm selector are chosen using a training set of typical problem instances from the application domain at hand. In this paper, we provide the first provable guarantees for portfolio-based algorithm selection. We analyze how large the training set should be to ensure that the resulting algorithm selector's average performance over the training set is close to its future (expected) performance. This involves analyzing three key reasons why these two quantities may diverge: 1) the learning-theoretic complexity of the algorithm selector, 2) the size of the portfolio, and 3) the learning-theoretic complexity of the algorithm's performance as a function of its parameters. We introduce an end-to-end learning-theoretic analysis of the portfolio construction and algorithm selection together. We prove that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector. With experiments, we illustrate a tradeoff exposed by our theoretical analysis: as we increase the portfolio size, we can hope to include a well-suited parameter setting for every possible problem instance, but it becomes impossible to avoid overfitting. 

   more » « less