Author name cluster

Michael Amir

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.

6 papers

2 author rows

AAAI Conference 2026 Conference Paper

Graph Attention-Guided Search for Dense Multi-Agent Pathfinding

Rishabh Jain
Keisuke Okumura
Michael Amir
Amanda Prorok

Finding near-optimal solutions for dense multi-agent pathfinding (MAPF) problems in real-time remains challenging even for state-of-the-art planners. To this end, we develop a hybrid framework that integrates a learned heuristic derived from MAGAT, a neural MAPF policy with a graph attention scheme, into a leading search-based algorithm, LaCAM. While prior work has explored learning-guided search in MAPF, such methods have historically underperformed. In contrast, our approach, termed LaGAT, outperforms both purely search-based and purely learning-based methods in dense scenarios. This is achieved through an enhanced MAGAT architecture, a pre-train–then–fine-tune strategy on maps of interest, and a deadlock detection scheme to account for imperfect neural guidance. Our results demonstrate that, when carefully designed, hybrid search offers a powerful solution for tightly coupled, challenging multi-agent coordination problems.

PDF Details DOI

TCS Journal 2024 Journal Article

Optimally reordering mobile agents on parallel rows

Dmitry Rabinovich
Michael Amir
Alfred M. Bruckstein

Given a collection of red and blue mobile agents located on two grid rows, we seek to move all the blue agents to the far left side and all the red agents to the far right side, thus physically sorting them according to color. The agents all start on the bottom row. They move simultaneously at discrete time steps and must not collide. Our goal is to design a centralized algorithm that controls the agents so as to sort them in the least number of time steps. We derive an exact lower bound on the amount of time any algorithm requires to sort a given initial configuration of agents. We find an instance optimal algorithm that provably matches this lower bound, attaining the best possible sorting time for any initial configuration. Surprisingly, we find that whenever the leftmost agent is red and the rightmost agent is blue, a straightforward decentralized and local sensing-based algorithm is at most 1 time step slower than the centralized instance-optimal algorithm.

Details DOI

IROS Conference 2023 Conference Paper

Competitive Ant Coverage: The Value of Pursuit

Alon Shats
Michael Amir
Noa Agmon

This paper studies the problem of Competitive Ant Coverage, in which two ant-like robots with very limited capabilities in terms of sensing range, computational power, and knowledge of the world compete in an area coverage task. We examine two variants of the problem that differ in the robot's objective: either being the First to Cover a Cell (FCC), or being the Last to Cover a Cell (LCC). Each robot's goal is to acquire (by visiting first or last, respectively) more cells than the opposing robot, and by that win the game. We examine the problem both theoretically and empirically, and show that the main strategy for dominance revolves around the ability to pursue: in LCC, we wish to pursue the opposing robot, whereas in FCC, we wish to create a scenario wherein the opposing robot pursues us. We find that this ability relies more heavily on knowledge of the opponent's strategy than on the robot's sensing capabilities. Moreover, given the robot's limited capabilities, we find that this knowledge-gap cannot be easily mitigated by learning.

Details

AAMAS Conference 2023 Conference Paper

Stigmergy-based, Dual-Layer Coverage of Unknown Regions

Ori Rappel
Michael Amir
Alfred M. Bruckstein

We present algorithms for uniformly covering an unknown indoor region with a swarm of simple, anonymous and autonomous mobile agents. The exploration of such regions is made difficult by the lack of a common global reference frame, severe degradation of radio-frequency communication, and ground obstacles. We propose addressing these challenges by using airborne agents, such as Micro Air Vehicles, in dual capacity, both as mobile explorers and, once they land, as beacons that help other agents navigate the region. The algorithms we propose are designed for a swarm of identical ant-like agents with local sensing capabilities. The agents enter the region, which is represented as a graph, over time from one or more entry points and are required to occupy all of its vertices. Unlike many works in this area, we consider the task of informing an outside operator with limited information that the coverage mission is complete. Even with this additional requirement we show, both through simulations and mathematical proofs, that the dual role concept results in linear-time termination, while also improving many well-known algorithms in the literature in terms of energy use.

PDF

AAMAS Conference 2019 Conference Paper

Minimizing Travel in the Uniform Dispersal Problem for Robotic Sensors

Michael Amir
Alfred M. Bruckstein

The limited energy capacity of individual robotic agents in a swarm often limits the possible cooperative tasks they can perform. In this work, we investigate the problem of covering an unknown connected grid environment (e. g. a maze or connected corridors) with a robotic swarm so as to minimize the maximal number of steps that each member of the swarm makes and their activity time before their work is finished, thereby minimizing the energy requirements. The robots are autonomous, anonymous and identical, with local sensors and finite memory, and possess no communication capabilities. They are assumed to disperse over time from a fixed location, and to move synchronously. The robots are tasked with occupying every cell of the environment, while avoiding collisions. In the literature such topics are known as uniform dispersal problems. The goal of minimizing the number of steps traveled by the robots has previously been studied in this context. Our contribution is a local robotic strategy for simply connected grid environments that, by exploiting their topology, achieves optimal makespan (the amount of time it takes to cover the environment) and minimizes the maximal number of steps taken by the individual robots before their deactivation. The robots succeed in discovering optimal paths to their eventual destinations, and finish the covering process in 2V − 1 time steps, where V is the number of cells in the environment.

PDF

TCS Journal 2019 Journal Article

Probabilistic pursuits on graphs

Michael Amir
Alfred M. Bruckstein

We consider discrete dynamical systems of “ant-like” agents engaged in a sequence of pursuits on a graph environment. The agents emerge one by one at equal time intervals from a source vertex s and pursue each other by greedily attempting to close the distance to their immediate predecessor, the agent that emerged just before them from s, until they arrive at the destination point t. Such pursuits have been investigated before in the continuous setting and in discrete time when the underlying environment is a regular grid. In both these settings the agents' walks provably converge to a shortest path from s to t. Furthermore, assuming a certain natural probability distribution over the move choices of the agents on the grid (in case there are multiple shortest paths between an agent and its predecessor), the walks converge to the uniform distribution over all shortest paths from s to t - and so the agents' locations are on average very close to the straight line from s to t. In this work we study the evolution of agent walks over a general finite graph environment G. Our model is a natural generalization of the pursuit rule proposed for the case of the grid. The main results are as follows. We show that “convergence” to the shortest paths in the sense of previous work extends to all pseudo-modular graphs (i. e. graphs in which every three pairwise intersecting disks have a nonempty intersection), and also to environments obtained by taking graph products, generalizing previous results in two different ways. We show that convergence to the shortest paths is also obtained by chordal graphs (i. e. graphs in which all cycles of four or more vertices have a chord), and discuss some further positive and negative results for planar graphs. In the most general case, convergence to the shortest paths is not guaranteed, and the agents may get stuck on sets of recurrent, non-optimal walks from s to t. However, we show that the limiting distributions of the agents' walks will always be uniform distributions over some set of walks of equal length.

Details DOI