Noa Agmon

IJCAI Conference 2025 Conference Paper

Decentralized Online Learning by Selfish Agents in Coalition Formation

• Saar Cohen
• Noa Agmon

Coalition formation involves self-organized coalitions generated through strategic interactions of autonomous selfish agents. In online learning of coalition structures, agents' preferences toward each other are initially unknown before agents interact. Coalitions are formed iteratively based on preferences that agents learn online from repeated feedback resulting from their interactions. In this paper, we introduce online learning in coalition formation through the lens of distributed decision-making, where self-interested agents operate without global coordination or information sharing, and learn only from their own experience. Under our selfish perspective, each agent seeks to maximize her own utility. Thus, we analyze the system in terms of Nash stability, where no agent can improve her utility by unilaterally deviating. We devise a sample-efficient decentralized algorithm for selfish agents that minimize their Nash regret, yielding approximately Nash stable solutions. In our algorithm, each agent uses only one utility feedback per round to update her strategy, but our algorithm still has Nash regret and sample complexity bounds that are optimal up to logarithmic factors.

AAMAS Conference 2025 Conference Paper

Egalitarianism in Online Coalition Formation

• Saar Cohen
• Noa Agmon

We investigate the online coalition formation problem, where agents arrive one by one and must be assigned to coalitions, with their utilities for others revealed upon arrival. Our focus lies on additively separable hedonic games, where agents assign cardinal utilities to others, assumed to be controlled by an adversary in our online context. This paper introduces the evaluation of partitions based on their egalitarian social welfare, with the goal of maximizing the minimum utility of any agent. This objective strikes balance between fairness and efficiency by prioritizing the satisfaction of the least well-off agents. For various real-life scenarios, we establish tight or nearly tight upper bounds on the competitive ratio and complement these findings with optimal or near-optimal algorithms. However, we also demonstrate that in some cases, no competitive algorithm is feasible. In particular, under the classic worst-case adversarial model, where agents arrive in an arbitrary order, we show that no algorithm has a non-trivial competitive ratio, if at all.

AAAI Conference 2025 Conference Paper

Online Learning of Coalition Structures by Selfish Agents

• Saar Cohen
• Noa Agmon

Coalition formation concerns autonomous agents that strategically interact to form self-organized coalitions. When agents lack initial sufficient information to evaluate their preferences before interacting with others, they learn them online through repeated feedback while iteratively forming coalitions. In this work, we introduce online learning in coalition formation from a non-cooperative perspective, studying the impact of collective data utilization where selfish agents aim to accelerate their learning by leveraging a shared data platform. Thus, the efficiency and dynamics of the learning process are affected by each agent's local feedbacks, motivating us to explore the tension between semi-bandit and bandit feedback, which differ in the granularity of utility information observed by each agent. Under our non-cooperative viewpoint, we evaluate the system by means of Nash stability, where no agent can improve her utility by unilaterally deviating. Our main result is a sample-efficient algorithm for selfish agents that aims to minimize their Nash regret under both semi-bandit and bandit feedback, implying approximately Nash stable outcomes. Under both feedback settings, our algorithm enjoys Nash regret and sample complexity bounds that are optimal up to logarithmic factors.

ECAI Conference 2025 Conference Paper

Online Learning of Fair Coalition Structures

• Saar Cohen 0001
• Noa Agmon

Coalition formation concerns partitioning agents into disjoint coalitions based on their preferences for one another. In online learning of coalition structures, agents’ true preferences may be initially unknown. Thus, coalitions are repeatedly formed based on preferences learned online from iterative feedback derived from interactions in those coalitions. This work introduces a new fairness-oriented approach to online learning in coalition formation, relying only on partial noisy feedback observed after agents interact. We analyze the system in terms of envy-based fairness notions. Envy-freeness is a popular criterion, where no agent prefers another agent’s coalition over her own. While trivial envy-free solutions exist for unconstrained number of coalitions and coalition sizes, constraints may make envy-free partitions unattainable. We thus present a new envy-freeness-based metric into hedonic games: minimax envy partitions, which minimize the maximum envy experienced by any agent. We devise an algorithm designed to minimize maximum envy, proven to attain sublinear envy regret.

JAIR Journal 2024 Journal Article

Collision Avoiding Max-Sum for Mobile Sensor Teams

• Arseniy Pertzovsky
• Roie Zivan
• Noa Agmon

Recent advances in technology have large teams of robots with limited computation skills work together in order to achieve a common goal. Their personal actions need to contribute to the joint effort, however, they also must assure that they do not harm the efforts of the other members of the team, e.g., as a result of collisions. We focus on the distributed target coverage problem, in which the team must cooperate in order to maximize utility from sensed targets, while avoiding collisions with other agents. State of the art solutions focus on the distributed optimization of the coverage task in the team level, while neglecting to consider collision avoidance, which could have far reaching consequences on the overall performance. Therefore, we propose CAMS: a collision-avoiding version of the Max-sum algorithm, for solving problems including mobile sensors. In CAMS, a factor-graph that includes two types of constraints (represented by function-nodes) is being iteratively generated and solved. The first type represents the task-related requirements, and the second represents collision avoidance constraints. We prove that consistent beliefs are sent by target representing function-nodes during the run of the algorithm, and identify factor-graph structures on which CAMS is guaranteed to converge to an optimal (collision-free) solution. We present an experimental evaluation in extensive simulations, showing that CAMS produces high quality collision-free coverage also in large and complex scenarios. We further present evidence from experiments in a real multi-robot system that CAMS outperforms the state of the art in terms of convergence time.

AAMAS Conference 2024 Conference Paper

Near-Optimal Online Resource Allocation in the Random-Order Model

• Saar Cohen
• Noa Agmon

We study the problem of allocating either divisible or indivisible items (goods or chores) among a set of agents, where the items arrive online, one at a time. Each agent’s non-negative value for an item is set by an adversary upon the item’s arrival. Our focus is on a unifying algorithmic framework for finding online allocations that treats both fairness and economic efficiency. For this sake, we aim to optimize the generalized means of agents’ received values, covering a spectrum of welfare functions including average utilitarian welfare and egalitarian welfare. In the traditional adversarial model, where items arrive in an arbitrary order, no algorithm can give a decent approximation to welfare in the worst case. To escape from this strong lower bound, we consider the random-order model, where items arrive in a uniformly random order. This model provides us with a major breakthrough: we devise algorithms that guarantee a nearly-optimal competitive ratio for certain welfare functions, if the welfare obtained by the optimal allocation is sufficiently large. We prove that our results are almost tight: if the optimal solution’s welfare is strictly below a certain threshold, then no nearly-optimal algorithm exists, even in the random-order model.

ECAI Conference 2024 Conference Paper

Online Friends Partitioning Under Uncertainty

• Saar Cohen 0001
• Noa Agmon

We study the friendship-based online coalition formation problem, in which agents that appear one at a time should be partitioned into coalitions, and an agent’s utility for a coalition is the number of her neighbors (i. e. , friends) within the coalition. Unlike prior work, agents’ friendships may be uncertain. We analyze the desirability of the resulting partition in the common term of optimality, aiming to maximize the social welfare. We design an online algorithm termed Maximum Predicted Coalitional Friends (MPCF), which is enhanced with predictions of each agent’s number of friends within any possible coalition. For common classes of random graphs, we prove that MPCF is optimal, and, for certain graphs, provides the same guarantee as the best known competitive algorithm for settings without uncertainty.

IJCAI Conference 2024 Conference Paper

Online Learning of Partitions in Additively Separable Hedonic Games

• Saar Cohen
• Noa Agmon

Coalition formation involves partitioning agents into disjoint coalitions based on their preferences over other agents. In reality, agents may lack enough information to assess their preferences before interacting with others. This motivates us to initiate the research on coalition formation from the viewpoint of online learning. At each round, a possibly different subset of a given set of agents arrives, that a learner then partitions into coalitions. Only afterwards, the agents' preferences, which possibly change over time, are revealed. The learner's goal is optimizing social cost by minimizing his (static or dynamic) regret. We show that even no-static regret is hard to approximate, and constant approximation in polynomial time is unattainable. Yet, for a fractional relaxation of our problem, we devise an algorithm that simultaneously gives the optimal static and dynamic regret. We then present a rounding scheme with an optimal dynamic regret, which converts our algorithm's output into a solution for our original problem.

AAMAS Conference 2023 Conference Paper

Anonymous Multi-Agent Path Finding with Individual Deadlines

• Gilad Fine
• Dor Atzmon
• Noa Agmon

Anonymous Multi-Agent Path Finding (AMAPF) is the problem of planning conflict-free paths to a set of target locations for a group of agents, where each agent is not associated with a specific target. This paper studies AMAPF with Individual Deadlines (AMAPFwID), where each target must be reached before a specific deadline, and the agent stays there to perform some long-term mission, for instance securing an asset, responding to an emergency, or performing a maintenance job. We examine three types of behavior of agents when reaching a target: (a) disappear on target, (b) stay on target, and (c) move after the deadline. The latter is only possible if the agent is replaced by another agent. We refer to this replacement as hot swapping. We propose a solution to AMAPFwID with each type of such behavior, based on a reduction to Network Flow. We test all solutions experimentally and show cases where hot swapping is beneficial. Finally, we also provide a solution to the case where agents disappear on targets that maximizes the number of targets reached and discuss other aspects of the problem.

AAMAS Conference 2023 Conference Paper

CAMS: Collision Avoiding Max-Sum for Mobile Sensor Teams

• Arseni Pertzovskiy
• Roie Zivan
• Noa Agmon

Recent advances in technology have large teams of robots with limited computation and communication skills work together in order to achieve a common goal. Their personal actions need to contribute to the joint effort, however, they also must assure that they do not harm the efforts of the other members of the team, e. g. , as a result of collisions. We focus on the distributed target coverage problem, in which the team must cooperate in order to maximize utility from sensed targets, while avoiding collisions with other agents. State of the art solutions focus on the distributed optimization of the coverage task in the team level, while neglecting to consider collision avoidance, which could have far reaching consequences on the overall performance. Therefore, we propose CAMS: a collision-avoiding version of the Max-sum algorithm, for solving problems including mobile sensors. In CAMS, a factor-graph that includes two types of constraints (represented by functionnodes) is being iteratively generated and solved. The first type represents the task-related requirements, and the second represents collision avoidance constraints. We prove that consistent beliefs are sent by target representing function-nodes during the run of the algorithm, and identify factor-graph structures on which CAMS is guaranteed to converge to an optimal (collision-free) solution. We present an empirical evaluation in extensive simulations, showing that CAMS produces high quality collision-free coverage also in large and complex scenarios. We further present evidence from experiments in a real multi-robot system that CAMS outperforms the state of the art in terms of convergence time.

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.

AAAI Conference 2023 Conference Paper

Complexity of Probabilistic Inference in Random Dichotomous Hedonic Games

• Saar Cohen
• Noa Agmon

Hedonic games model cooperative games where agents desire to form coalitions, and only care about the composition of the coalitions of which they are members. Focusing on various classes of dichotomous hedonic games, where each agent either approves or disapproves a given coalition, we propose the random extension, where players have an independent participation probability. We initiate the research on the computational complexity of computing the probability that coalitions and partitions are optimal or stable. While some cases admit efficient algorithms (e.g., agents approve only few coalitions), they become computationally hard (#P-hard) in their complementary scenario. We then investigate the distribution of coalitions in perfect partitions and their performance in majority games, where an agent approves coalitions in which the agent is friends with the majority of its members. When friendships independently form with a constant probability, we prove that the number of coalitions of size 3 converges in distribution to a Poisson random variable.

AAMAS Conference 2023 Conference Paper

Online Coalitional Skill Formation

• Saar Cohen
• Noa Agmon

Efficiently allocating heterogeneous tasks to agents that arrive dynamically and have diverse skills is a central problem in multi-agent systems called online task allocation. In many cases, a single agent does not meet the skill levels required by a particular task, which incentivizes the agents to form coalitions for handling it. In this paper, we propose a new framework, termed as online coalitional skill formation (OCSF), for handling online task allocation via coalition formation, where tasks require different skills for being successfully fulfilled, and each agent has different levels at mastering each skill. The goal of the organizer is therefore to assign agents that arrive online to a coalition responsible for performing some task, so as to optimally approach the desired skill levels of all tasks. Focusing on the case in which the set of possible mastering levels for each skill is discrete, we suggest different assignment algorithms based on the knowledge the organizer has on the arriving agents. When agents arrive i. i. d. according to some unknown distribution, we propose a greedy and adaptive scheme that assigns an agent to a task, proving a tight bound on the system’s performance. If the distribution is known, we devise a novel correlation to Constrained Markov Decision Processes whose goal is maximizing the rate at which agents are assigned to each task while respecting their requirements. We then construct a non-adaptive approach that terminates when all the tasks’ requirements are met. Finally, if the distribution is unknown, we provide two algorithms that learn it online. We have fully implemented the algorithms, showing that in many cases a higher diversity in skills may yield poor assignments.

IROS Conference 2022 Conference Paper

Multi-Robot Dynamic Swarm Disablement

• Ori Fogler
• Noa Agmon

Motivated by the use of robots for pest control in agriculture, this work introduces the Multi-Robot Dynamic Swarm Disablement problem, in which a team of robots is required to disable a swarm of agents (for example, locust agents) passing through an area while minimizing the cumulative time of the swarm members (equivalent to the cumulative damage they cause) in the area. Showing that the problem is hard even in naive settings, we turn to examine algorithms seeking to optimize the robots' performance against the swarm by exploiting the known movement pattern of the swarm agents. Motivated by the poor performance when a weak group of robots attempts to catch a large swarm of agents, whether it is a significant numerical minority or poor speed gaps, we suggest the use of blocking lines: the robots form lines that block the agents along their movement in the environment. We show by both theoretical analysis and rigorous empirical evaluation in different settings that these algorithms outperform common task-assignment-based algorithms, especially for limited robots versus a large swarm.

AAMAS Conference 2022 Conference Paper

Optimizing Multi-Agent Coordination via Hierarchical Graph Probabilistic Recursive Reasoning

• Saar Cohen
• Noa Agmon

Multi-agent reinforcement learning (MARL) requires coordination by some means of interaction between agents to efficiently solve tasks. Interaction graphs allow reasoning about joint actions based on the local structure of interactions, but they disregard the potential impact of an agent’s action on its neighbors’ behaviors, which could rapidly alter in dynamic settings. In this paper, we thus present a novel perspective on opponent modeling in domains with only local interactions using (level-1) Graph Probabilistic Recursive Reasoning (GrPR2). Unlike previous work on recursive reasoning, each agent iteratively best-responds to other agents’ policies over all possible local interactions. Agents’ policies are approximated via a variational Bayes scheme for capturing their uncertainties, and we prove that an induced variant of Q-learning converges under self-play when there exists only one Nash equilibrium. In cooperative settings, we further devise a variational lower bound on the likelihood of each agent’s optimality. Opposed to other models, optimizing the resulting objective prevents each agent from attaining an unrealistic modelling of others, and yields an exact tabular Q-iteration method that holds convergence guarantees. Then, we deepen the recursion to level-𝑘 via Cognitive Hierarchy GrPR2 (GrPR2-CH), which lets each level-𝑘 player best-respond to a mixture of strictly lower levels in the hierarchy. We prove that: (1) level-3 reasoning is the optimal hierarchical level, maximizing each agent’s expected return; and (2) the weak spot of the classical CH models is that 0-level is uniformly distributed, as it may introduce policy bias. Finally, we propose a practical actorcritic scheme, and illustrate that GrPR2-CH outperforms strong MARL baselines in the particle environment.

IJCAI Conference 2021 Conference Paper

Convexified Graph Neural Networks for Distributed Control in Robotic Swarms

• Saar Cohen
• Noa Agmon

A network of robots can be viewed as a signal graph, describing the underlying network topology with naturally distributed architectures, whose nodes are assigned to data values associated with each robot. Graph neural networks (GNNs) learn representations from signal graphs, thus making them well-suited candidates for learning distributed controllers. Oftentimes, existing GNN architectures assume ideal scenarios, while ignoring the possibility that this distributed graph may change along time due to link failures or topology variations, which can be found in dynamic settings. A mismatch between the graphs on which GNNs were trained and the ones on which they are tested is thus formed. Utilizing online learning, GNNs can be retrained at testing time, overcoming this issue. However, most online algorithms are centralized and work on convex problems (which GNNs scarcely lead to). This paper introduces novel architectures which solve the convexity restriction and can be easily updated in a distributed, online manner. Finally, we provide experiments, showing how these models can be applied to optimizing formation control in a swarm of flocking robots.

IROS Conference 2021 Conference Paper

Hybrid Path Planning for UAV Traffic Management

• Eyal Zehavi
• Noa Agmon

Unmanned Aircraft System Traffic Management (UTM) becomes a highly relevant complex challenge, as the UAV activity is rapidly growing bringing more amateur and professional drones to the urban skies. The main concern of managing such a system is safely navigating and controlling hundreds or thousands of drones simultaneously, flying in a crowded dense environments. This paper introduces an innovative approach of hybrid path planning, which tries to make the best out of the commonly used centralized and decentralized planning approaches. The Hybrid Path Planner (HPP) defines two configuration spaces: the Local Zone, which represents the crowded city zone with many obstacles and constrains, and the Global Zone, which represents the outer suburban zone, mostly open space with predefined flight corridors. The HPP server communicates with each UAV, assigning it a close-to-optimal path in the global zone, while leaving the relatively heavy-duty local zone path planning task to be performed by the UAV, mostly using stochastic methods like RRT *. This approach reduces the complex path panning task of the centralized server to a simpler task of calculating only the entry and exit points to and from the global zone. This robust approach supports handling a high number of UAVs, while keeping close to optimal performance.

AAMAS Conference 2021 Conference Paper

Spatial Consensus-Prevention in Robotic Swarms

• Saar Cohen
• Noa Agmon

In this work, we define the consensus-prevention problem, which examines the canonical swarm robotic consensus problem from an adversarial point of view: how (if at all) is it possible to lead a swarm into a disagreement, that is, prevent them from reaching an agreement. We focus on consensus-prevention in physically grounded tasks, concentrating on influencing the direction of movement of a flocking swarm and guaranteeing that the swarm will never converge to the same direction by the use of external, predefined agents, referred to as diverting agents. We formally define the notion of disagreement within a flock, and propose a way of measuring it. We show a correlation between the consensus-prevention problem and the coalition formation problem, whose players aim at maximizing the disagreement measure. While the general problem of optimizing disagreement between flocking agents is NP-hard, we focus on a case which is solvable in polynomial time, using a variant of the graph clustering problem where the clusters constitute the desired coalitions. This allows us to determine both the number of coalitions that optimize disagreement, and the behavior of the diverting agents for a given number of coalitions that will lead to optimal disagreement. Finally, we demonstrate in simulation the impact of the number of diverting agents on the disagreement measure in different scenarios, and discuss the limitations of the diverting agents in dynamic settings.

AAAI Conference 2020 Conference Paper

Adversarial Fence Patrolling: Non-Uniform Policies for Asymmetric Environments

• Yaniv Oshrat
• Noa Agmon
• Sarit Kraus

Robot teams are very useful in patrol tasks, where the robots are required to repeatedly visit a target area in order to detect an adversary. In this work we examine the Fence Patrol problem, in which the robots must travel back and forth along an open polyline and the adversary is aware of the robots’ patrol strategy. Previous work has suggested nondeterministic patrol schemes, characterized by a uniform policy along the entire area, guaranteeing that the minimal probability of penetration detection throughout the area is maximized. We present a patrol strategy with a non-uniform policy along different points of the fence, based on the location and other properties of the point. We explore this strategy in different kinds of tracks and show that the minimal probability of penetration detection achieved by this non-uniform (variant) policy is higher than former policies. We further consider applying this model in multi-robot scenarios, exploiting robot cooperation to enhance patrol efficiency. We propose novel methods for calculating the variant values, and demonstrate their performance empirically.

IROS Conference 2020 Conference Paper

Competitive Coverage: (Full) Information as a Game Changer

• Moshe N. Samson
• Noa Agmon

This paper introduces the competitive coverage problem, a new variant of the robotic coverage problem in which a robot R competes with another robot O in order to be the first to cover an area. In the variant discussed in this paper, the asymmetric competitive coverage, O is unaware of the existence of R, which attempts to take that fact into consideration in order to succeed in being the first to cover as many parts of the environment as possible. We consider different information models of R that define how much it knows about the location of O and its planned coverage path. We present an optimal algorithm for R in the full-information case, and show that unless R has information about O's initial location, it is as if it has no information at all. Lastly, we describe a correlation between the time it takes R to reach O's initial location and the coverage paths quality, and present a heuristic algorithm for the case in which R has information only about O's initial location, showing its superiority compared to other coverage algorithms in rigorous simulation experiments.

ICML Conference 2020 Conference Paper

Explicit Gradient Learning for Black-Box Optimization

• Elad Sarafian
• Mor Sinay
• Yoram Louzoun
• Noa Agmon
• Sarit Kraus

Black-Box Optimization (BBO) methods can find optimal policies for systems that interact with complex environments with no analytical representation. As such, they are of interest in many Artificial Intelligence (AI) domains. Yet classical BBO methods fall short in high-dimensional non-convex problems. They are thus often overlooked in real-world AI tasks. Here we present a BBO method, termed Explicit Gradient Learning (EGL), that is designed to optimize high-dimensional ill-behaved functions. We derive EGL by finding weak spots in methods that fit the objective function with a parametric Neural Network (NN) model and obtain the gradient signal by calculating the parametric gradient. Instead of fitting the function, EGL trains a NN to estimate the objective gradient directly. We prove the convergence of EGL to a stationary point and its robustness in the optimization of integrable functions. We evaluate EGL and achieve state-of-the-art results in two challenging problems: (1) the COCO test suite against an assortment of standard BBO methods; and (2) in a high-dimensional non-convex image generation task.

IROS Conference 2020 Conference Paper

Multi-Robot Containment and Disablement

• Yuval Maymon
• Noa Agmon

This paper presents the multi-robot containment and disablement (CAD) problem. In this problem, a team of (ground or aerial) robots are engaged in a cooperative task of swarm containment and disablement (for example, locust swarm). Each team member is equipped with a tool that can both detect and disable the swarm individuals. The swarm is active in a given physical location, and the goal of the robots is twofold: to contain the swarm members such that the individuals will be prevented from expanding further beyond this area (this is referred to as perfect enclosure), and to fully disable the locust by reducing the size of the contained area (while preserving the perfect enclosure). We determine the minimal number of robots necessary to ensure perfect enclosure, and a placement of the robots about the contained area such that they will be able to guarantee perfect enclosure, as well as a distributed area reduction protocol maintaining perfect enclosure. We then suggest algorithms for handling the case in which there are not enough robots to guarantee perfect enclosure, and describe their performance based on rigorous experiments in the TeamBots simulator.

AIJ Journal 2019 Journal Article

Multi-robot adversarial patrolling: Handling sequential attacks

• Efrat Sless Lin
• Noa Agmon
• Sarit Kraus

Robot teams are commonly used for security tasks, where they are required to repeatedly monitor an area in order to prevent penetrations, initiated by an adversary. Current research in this field focuses mainly on detecting penetration attempts, but not on responding. Requiring the robots to also inspect and handle the penetrations has a significant impact on the patrol, as each penetration attempt also influences the robots' behavior, making them vulnerable to multiple attacks. Moreover, a knowledgeable adversary can initiate two sequential attacks, where the second attempt exploits the vulnerable points caused by the requirement that a robot handle the first penetration attempt. In this work, we consider the problem of sequential attacks and examine different robot policies against such adversarial behavior. We provide an optimal patrol strategy for various penetration attempt patterns. Our novel approach considers a full history-length policy, while previous work only handled very limited lengths of history. The use of a longer history improves the results. Moreover, we show how to significantly reduce, in practice, the exponential space state of the problem, while maintaining the optimality of the solution.

JAAMAS Journal 2018 Journal Article

Capturing an area-covering robot

• Roi Yehoshua
• Noa Agmon

Abstract Area coverage is a fundamental task in robotics, where one or more robots are required to visit all points in a target area at least once. In many real-world scenarios, the need arises for protecting one’s territory from being covered by a robot, e. g. , when we need to defend a building from being surveyed by an adversarial force. Therefore, this paper discusses the problem of defending a given area from being covered by a robot. In this problem, the defender needs to choose the locations of k stationary guards in the target area, each one having some probability of capturing the robot, in a way that maximizes the probability of stopping the covering robot. We consider two types of covering robots: one that has an a-priori map of the environment, including the locations of the guards; and the other has no prior knowledge of the environment, and thus has to use real-time sensor measurements in order to detect the guards and plan its path according to their discovered locations. We show that in both cases the defender can exploit the target area’s topology, and specifically the vulnerability points in the area (i. e. , places that must be visited by the robot more than once), in order to increase its chances of capturing the covering robot. We also show that although in general finding an optimal strategy for a defender with zero-knowledge on the robot’s coverage strategy is \({\mathcal {NP}}\) -Hard, for certain values of k an optimal strategy can be found in polynomial time. For other cases we suggest heuristics that can significantly outperform the random baseline strategy. We provide both theoretical and empirical evaluation of our suggested algorithms.

AAMAS Conference 2018 Conference Paper

Distributed Accurate Formation Control Under Uncertainty

• Dany Rovinsky
• Noa Agmon

Formation control is a canonical task in the multi-robot teamwork field, where a group of robots is required to maintain a specific geometric pattern, while moving from a start point to a destination. When one assumes imperfection of the sensors of the robots, the goal becomes minimizing the group’s deviation from the required pattern (maximizing the formation accuracy). Previous work has considered optimality in an uncertain environment only in centralized setting (or using some form of communication). This work examines the problem of optimal formation accuracy in a distributed setting, while accounting for sensory uncertainty and no communication.

AAAI Conference 2018 Conference Paper

Plan Recognition in Continuous Domains

• Gal Kaminka
• Mor Vered
• Noa Agmon

Plan recognition is the task of inferring the plan of an agent, based on an incomplete sequence of its observed actions. Previous formulations of plan recognition commit early to discretizations of the environment and the observed agent’s actions. This leads to reduced recognition accuracy. To address this, we first provide a formalization of recognition problems which admits continuous environments, as well as discrete domains. We then show that through mirroring— generalizing plan-recognition by planning—we can apply continuous-world motion planners in plan recognition. We provide formal arguments for the usefulness of mirroring, and empirically evaluate mirroring in more than a thousand recognition problems in three continuous domains and six classical planning domains.

AAMAS Conference 2018 Conference Paper

Scheduling Spare Drones for Persistent Task Performance under Energy Constraints

• Erez Hartuv
• Noa Agmon
• Sarit Kraus

This paper considers the problem of enabling persistent execution of a multi-drone task under energy limitations. The drones are given a set of locations and their task is to ensure that at least one drone will be present, for example for monitoring, over each location at any given time. Because of energy limitations, drones must be replaced from time to time, and fly back home where their batteries can be replaced. Our goals are to identify the minimum number of spare drones needed to accomplish the task while no drone battery drains, and to provide a drone replacement strategy. We present an efficient procedure for calculating whether one spare drone is enough for a given task and provide an optimal replacement strategy. If more than one drone is needed, we aim at finding the minimum number of spare drones required, and extend the replacement strategy to multiple spare drones by introducing a new Bin-Packing variant, named Bin Maximum Item Double Packing (BMIDP). Since the problem is presumably computationally hard, we provide a first fit greedy approximation algorithm for efficiently solving the BMIDP problem. For the offline version, in which all locations are known in advance, we prove an approximation factor upper bound of 1. 5, and for the online version, in which locations are given one by one, we show via extensive simulations, that the approximation yields an average factor of 1. 7.

IROS Conference 2018 Conference Paper

UAV/UGV Search and Capture of Goal-Oriented Uncertain Targets*This research was supported in part by ISF grant #1337/15 and part by a grant from MOST, Israel and the JST Japan

• Mor Sinay
• Noa Agmon
• Oleg Maksimov
• Guy Levy
• Moshe Bitan
• Sarit Kraus

This paper considers a new, complex problem of UAV/UGV collaborative efforts to search and capture attackers under uncertainty. The goal of the defenders (UAV/UGV team) is to stop all attackers as quickly as possible, before they arrive at their selected goal. The uncertainty considered is twofold: the defenders do not know the attackers' location and destination, and there is also uncertainty in the defenders' sensing. We suggest a real-time algorithmic framework for the defenders, combining entropy and stochastic-temporal belief, that aims at optimizing the probability of a quick and successful capture of all of the attackers. We have empirically evaluated the algorithmic framework, and have shown its efficiency and significant performance improvement compared to other solutions.

IROS Conference 2018 Conference Paper

Uncertain Local Leader Selection in Distributed Formations

• Dany Rovinsky
• Noa Agmon

Leader-Follower is a hierarchical form of multi-robot formation control, where each robot aims to maintain specific predefined angle and distance from one or more robots in the team (referred to as its local leaders), while a single robot is selected to lead the entire formation to a desired destination. When the robots are given a specific formation to maintain, their goal is usually to minimize the deviation from this desired formation (maximizing the accuracy) during their journey. Previous work has considered optimality in an uncertain environment only in centralized setting (or using perfect, or almost perfect communication). In this paper we examine the problem of optimal multi-robot formation control in a distributed setting, while accounting for two challenges: sensory uncertainty and absence of communication. Specifically, we present an algorithm that allows each individual robot to estimate the overall formation accuracy of the other robots in their field of view via a tree reconstruction algorithm. The algorithm is used to select the most accurate local leader, or to generate virtual local leader via a weighted average of all visible robots. We provide both theoretical analysis and an extensive empirical evaluation (in ROS/Gazebo simulated environment) showing the effectiveness of the two approaches.

AAMAS Conference 2017 Conference Paper

Finding a Needle in a Haystack: Satellite Detection of Moving Objects in Marine Environments

• Natalie Fridman
• Doron Amir
• Ilan Schvartzman
• Oded Stawitzky
• Igor Kleinerman
• Sharon Kligsberg
• Noa Agmon

AIJ Journal 2017 Journal Article

Intelligent agent supporting human–multi-robot team collaboration

• Ariel Rosenfeld
• Noa Agmon
• Oleg Maksimov
• Sarit Kraus

The number of multi-robot systems deployed in field applications has risen dramatically over the years. Nevertheless, supervising and operating multiple robots simultaneously is a difficult task for a single operator to execute. In this article we propose a novel approach for utilizing automated advising agents in assisting an operator to better manage a team of multiple robots in complex environments. We introduce an advice provision methodology and exemplify its implementation using automated advising agents in two real-world human–multi-robot team collaboration tasks: the Search And Rescue (SAR) and the warehouse operation tasks. Our intelligent advising agents were evaluated through extensive field trials, with over 150 human operators using both simulated and physical mobile robots, and showed a significant improvement in the team's performance.

IJCAI Conference 2017 Conference Paper

Maintaining Communication in Multi-Robot Tree Coverage

• Mor Sinay
• Noa Agmon
• Oleg Maksimov
• Sarit Kraus
• David Peleg

Area coverage is an important task for mobile robots, mainly due to its applicability in many domains, such as search and rescue. In this paper we study the problem of multi-robot coverage, in which the robots must obey a strong communication restriction: they should maintain connectivity between teammates throughout the coverage. We formally describe the Multi-Robot Connected Tree Coverage problem, and an algorithm for covering perfect N-ary trees while adhering to the communication requirement. The algorithm is analyzed theoretically, providing guarantees for coverage time by the notion of speedup factor. We enhance the theoretically-proven solution with a dripping heuristic algorithm, and show in extensive simulations that it significantly decreases the coverage time. The algorithm is then adjusted to general (not necessarily perfect) N-ary trees and additional experiments prove its efficiency. Furthermore, we show the use of our solution in a simulated officebuilding scenario. Finally, we deploy our algorithm on real robots in a real office building setting, showing efficient coverage time in practice.

IJCAI Conference 2017 Conference Paper

On the Power and Limitations of Deception in Multi-Robot Adversarial Patrolling

• Noga Talmor
• Noa Agmon

Multi-robot adversarial patrolling is a well studied problem, investigating how defenders can optimally use all given resources for maximizing the probability of detecting penetrations, that are controlled by an adversary. It is commonly assumed that the adversary in this problem is rational, thus uses the knowledge it has on the patrolling robots (namely, the number of robots, their location, characteristics and strategy) to optimize its own chances to penetrate successfully. In this paper we present a novel defending approach which manipulates the adversarial (possibly partial) knowledge on the patrolling robots, so that it will believe the robots have more power than they actually have. We describe two different ways of deceiving the adversary: Window Deception, in which it is assumed that the adversary has partial observability of the perimeter, and Scarecrow Deception, in which some of the patrolling robots only appear as real robots, though they have no ability to actually detect the adversary. We analyze the limitations of both models, and suggest a random-based approach for optimally deceiving the adversary that considers both the resources of the defenders, and the adversarial knowledge.

IJCAI Conference 2017 Conference Paper

Robotic Strategic Behavior in Adversarial Environments

• Noa Agmon

The presence of robots in areas containing threats is becoming more prevalent, due to their ability to perform missions accurately, efficiently, and with little risk to humans. Having the robots handle adversarial forces in missions such as search and rescue, intelligence gathering, border protection and humanitarian assistance, raises many new, exciting research challenges. This paper describes recent research achievements in areas related to robotic mission planning in adversarial environments, including multi-robot patrolling, robotic coverage, multi-robot formation, and navigation, and suggests possible future research directions.

AAMAS Conference 2017 Conference Paper

Safety First: Strategic Navigation in Adversarial Environments

• Ofri Keidar
• Noa Agmon

This work deals with the problem of navigation while avoiding detection by a mobile adversary, which is a novel variant of pursuit-evasion featuring adversarial modeling. In this problem, an evading agent is placed on a graph, where one or more nodes are defined as safehouses. The agent’s goal is to find a path from its current location to a safehouse, while minimizing the probability of meeting a mobile adversarial agent at a node along its path (i. e. , being captured). We examine several models of this problem, where each one has different assumptions on what the agents know about their opponent, all using a framework for computing node utility, introduced herein. We use several risk attitudes for computing the utility values, whose impact on the constructed strategies is analyzed both theoretically and empirically. Furthermore, we allow the agents to use information gained along their movement, in order to efficiently update their motion strategies on-the-fly. Analytic and empirical analysis show the importance of using this information and these on-the-fly strategy updates.

ECAI Conference 2016 Conference Paper

Multi-Robot Adversarial Coverage

• Roi Yehoshua
• Noa Agmon

This work discusses the problem of adversarial coverage, in which one or more robots are required to visit every point of a given area, which contains threats that might stop the robots. The objective of the robots is to cover the target area as quickly as possible, while maximizing the percentage of covered area before they are stopped. This problem has many real-world applications, from performing coverage missions in hazardous fields such as nuclear power plants, to surveillance of enemy forces in the battlefield and field demining. Previous studies of the problem dealt with single-robot coverage. Using a multi-robot team for the coverage has clear advantages in terms of both coverage time and robustness: even if one robot is totally damaged, others may take over its coverage subtask. Hence, in this paper we describe a multi-robot coverage algorithm for adversarial environments that tries to maximize the percentage of covered area before the team is stopped, while minimizing the coverage time. We analytically show that the algorithm is robust, in that as long as a single robot is able to move, the coverage will be completed. We also establish theoretical bounds on the minimum covered area guaranteed by the algorithm and on the coverage time. Lastly, we evaluate the effectiveness of the algorithm in an extensive set of environments and settings.

IJCAI Conference 2016 Conference Paper

Rule-Based Programming of Molecular Robot Swarms for Biomedical Applications

• Inbal Wiesel-Kapah
• Gal A. Kaminka
• Guy Hachmon
• Noa Agmon
• Ido Bachelet

Molecular robots (nanobots) are being developed for biomedical applications, e. g. , to deliver medications without worrying about side-effects. Future treatments will require swarms of heterogeneous nanobots. We present a novel approach to generating such swarms from a treatment program. A compiler translates medications, written in a rule-based language, into specifications of a swarm built by specializing generic nanobot platforms to specific pay-loads and action-triggering behavior. The mixture of nanobots, when deployed, carries out the treatment program. We describe the medication programming language, and the associated compiler. We prove the validity of the compiler output, and report on in-vitro experiments using generated nanobot swarms.

ECAI Conference 2016 Conference Paper

Strategic Path Planning Allowing on-the-Fly Updates

• Ofri Keidar
• Noa Agmon

This work deals with the problem of strategic path planning while avoiding detection by a mobile adversary. In this problem, an evading agent is placed on a graph, where one or more nodes are defined as safehouses. The agent's goal is to find a path from its current location to a safehouse, while minimizing the probability of meeting a mobile adversarial agent at a node along its path (i. e. , being captured). We examine several models of this problem, where each one has different assumptions on what the agents know about their opponent, all using a framework for computing node utility. We use several risk attitudes for computing the utility values, whose impact on the actual performance of the path planning algorithms is highlighted by an empirical analysis. Furthermore, we allow the agents to use information gained along their movement, in order to efficiently update their motion strategies on-the-fly. Analytic and empiric analysis show that on-the-fly updates increase the probability that our agent reaches its destination safely.

JAAMAS Journal 2015 Journal Article

Agent development as a strategy shaper

• Avshalom Elmalech
• David Sarne
• Noa Agmon

Abstract This paper studies to what extent agent development changes one’s own strategy. While this question has many general implications it is of special interest to the study of peer designed agents (PDAs), which are computer agents developed by non-experts. This latter emerging technology, has been widely advocated in recent literature for the purpose of replacing people in simulations and investigating human behavior. Its main premise is that strategies programmed into these agents reliably reflect, to some extent, the behavior used by their programmers in real life. We show that PDA development has an important side effect that has not been addressed to date—the process that merely attempts to capture one’s strategy is also likely to affect the developer’s strategy. This result has many implications concerning the appropriate design of PDA-based simulations as well as the validity of using PDAs for studying individual decision making. The phenomenon is demonstrated experimentally, using two very different application domains and several performance measures. Our findings suggest that the effects on one’s strategy arise both in situations where it is potentially possible for people to reason about the optimal strategy (in which case PDA development will enhance the use of an optimal strategy) and in those where calculating the optimal strategy is computationally challenging (in which case PDA development will push people to use more effective strategies, on average). Since in our experiments PDA development actually improved the developer’s strategy, PDA development can be suggested as a means for improving people’s problem solving skills. Finally, we show that the improvement achieved in people’s strategies through agent development is not attributed to the expressive aspect of agent development per-se but rather there is a crucial additional gain in the process of designing and programming ones strategy into an agent.

IJCAI Conference 2015 Conference Paper

Intelligent Agent Supporting Human-Multi-Robot Team Collaboration

• Ariel Rosenfeld
• Noa Agmon
• Oleg Maksimov
• Amos Azaria
• Sarit Kraus

The number of multi-robot systems deployed in field applications has risen dramatically over the years. Nevertheless, supervising and operating multiple robots at once is a difficult task for a single operator to execute. In this paper we propose a novel approach for utilizing advising automated agents when assisting an operator to better manage a team of multiple robots in complex environments. We introduce the Myopic Advice Optimization (MYAO) Problem and exemplify its implementation using an agent for the Search And Rescue (SAR) task. Our intelligent advising agent was evaluated through extensive field trials, with 44 non-expert human operators and 10 low-cost mobile robots, in simulation and physical deployment, and showed a significant improvement in both team performance and the operator’s satisfaction.

IROS Conference 2015 Conference Paper

Online robotic adversarial coverage

• Roi Yehoshua
• Noa Agmon

In the robotic coverage problem, a robot is required to visit every point of a given area using the shortest possible path. In a recently introduced version of the problem, adversarial coverage, the covering robot operates in an environment that contains threats that might stop it. Previous studies of this problem dealt with finding optimal strategies for the coverage, that minimize both the coverage time and the probability that the robot will be stopped before completing the coverage. However, these studies assumed that a map of the environment, which includes the specific locations of the threats, is given to the robot in advance. In this paper, we deal with the online version of the problem, in which the covering robot has no a-priori knowledge of the environment, and thus has to use real-time sensor measurements in order to detect the threats. We employ a frontier-based coverage strategy that determines the best frontier to be visited by taking into account both the cost of moving to the frontier and the safety of the region that is reachable from it. We also examine the effect of the robot's sensing capabilities on the expected coverage percentage. Finally, we compare the performance of the online algorithm to its offline counterparts under various environmental conditions.

IROS Conference 2015 Conference Paper

Path planning for optimizing survivability of multi-robot formation in adversarial environments

• Yaniv Shapira
• Noa Agmon

Multi robot formation is a canonical problem in robotic research. The problem has been examined in neutral environments, where the robots' goal is usually to maintain the formation despite changes in the environment. The problem of multi robot formation has been motivated by natural phenomena such as schools of fish or flocks of birds. While in the natural phenomena the team behavior is responsive to threats, in robotics research of team formation, adversarial presence has been ignored. In this paper we present the problem of adversarial formation, in which a team of robots travels in a connected formation through an adversarial environment that includes threats that may harm the robots. The robots' goal is, therefore, to maximize their chance of traveling through the environment unharmed, where the formation may be used as a mean to achieve this goal. We formally define the problem, present a quantitative measure for evaluating the survivability of the team, and suggest possible solutions to a variant of the problem under certain threat characteristics, optimizing different team survivability criteria. Finally, we discuss the challenges raised by transitioning the discrete representation to a continuous environment in simulation.

AAAI Conference 2014 Conference Paper

Can Agent Development Affect Developer’s Strategy?

• Avshalom Elmalech
• David Sarne
• Noa Agmon

Peer Designed Agents (PDAs), computer agents developed by non-experts, is an emerging technology, widely advocated in recent literature for the purpose of replacing people in simulations and investigating human behavior. Its main premise is that strategies programmed into these agents reliably reflect, to some extent, the behavior used by their programmers in real life. In this paper we show that PDA development has an important side effect that has not been addressed to date — the process that merely attempts to capture one’s strategy is also likely to affect the developer’s strategy. The phenomenon is demonstrated experimentally, using several performance measures. This result has many implications concerning the appropriate design of PDA-based simulations, and the validity of using PDAs for studying individual decision making. Furthermore, we obtain that PDA development actually improved the developer’s strategy according to all performance measures. Therefore, PDA development can be suggested as a means for improving people’s problem solving skills.

ECAI Conference 2014 Conference Paper

Communicating with Unknown Teammates

• Samuel Barrett
• Noa Agmon
• Noam Hazon
• Sarit Kraus
• Peter Stone 0001

Past research has investigated a number of methods for coordinating teams of agents, but with the growing number of sources of agents, it is likely that agents will encounter teammates that do not share their coordination methods. Therefore, it is desirable for agents to adapt to these teammates, forming an effective ad hoc team. Past ad hoc teamwork research has focused on cases where the agents do not directly communicate. However when teammates do communicate, it can provide a valuable channel for coordination. Therefore, this paper tackles the problem of communication in ad hoc teams, introducing a minimal version of the multiagent, multiarmed bandit problem with limited communication between the agents. The theoretical results in this paper prove that this problem setting can be solved in polynomial time when the agent knows the set of possible teammates. Furthermore, the empirical results show that an agent can cooperate with a variety of teammates following unknown behaviors even when its models of these teammates are imperfect.

IROS Conference 2014 Conference Paper

Safest path adversarial coverage

• Roi Yehoshua
• Noa Agmon
• Gal A. Kaminka

Coverage is a fundamental problem in robotics, where one or more robots are required to visit each point in a target area at least once. While most previous work concentrated on finding a solution that completes the coverage as quickly as possible, in this paper we consider a new version of the problem: adversarial coverage. Here, the robot operates in an environment that contains threats that might stop the robot. We introduce the problem of finding the safest adversarial coverage path, and present different optimization criteria for the evaluation of these paths. We show that finding an optimal solution to the safest coverage problem is NP-Complete. We therefore suggest two heuristic algorithms: STAC, a spanning-tree based coverage algorithm, and GSAC, which follows a greedy approach. These algorithms produce close to optimal solutions in polynomial time. We establish theoretical bounds on the total risk involved in the coverage paths created by these algorithms and on their lengths. Lastly, we compare the effectiveness of these two algorithms in various types of environments and settings.

RLDM Conference 2013 Conference Abstract

Communicating with Unknown Teammates

• Samuel Barrett
• Noa Agmon
• Noam Hazon
• Sarit Kraus
• Peter Stone

Teamwork is central to many tasks, and past research has introduced a number of methods for coordinating teams of agents. However, with the growing number of sources of agents, it is likely that an agent will encounter teammates that do not share its coordination method. Therefore, it is desirable for agents to adapt to these teammates, forming an effective ad hoc team. Past ad hoc teamwork research has focused on cases where the agents do not directly communicate. This paper tackles the problem of communication in ad hoc teams, introducing a minimal version of the multiagent, multi-armed bandit problem with limited communication between the agents. The theoretical results in this paper prove that this problem setting can be solved in polynomial time when the agent knows the set of possible teammates. Furthermore, the empirical results show that an agent can cooperate with a variety of teammates not created by the authors even when its models of these teammates are imperfect.

IROS Conference 2013 Conference Paper

Robotic adversarial coverage: Introduction and preliminary results

• Roi Yehoshua
• Noa Agmon
• Gal A. Kaminka

This paper discusses the problem of generating efficient coverage paths for a mobile robot in an adversarial environment, where threats exist that might stop the robot. First, we formally define the problem of adversarial coverage, and present optimization criteria used for evaluation of coverage algorithms in adversarial environments. We then present a coverage area planning algorithm based on a map of the probable threats. The algorithm tries to minimize the total risk involved in covering the target area while taking into account coverage time constrains. The algorithm is based on incrementally extending the coverage path to the nearest safe cells while allowing the robot to repeat its steps. By allowing the robot to visit each cell in the target area more than once, the accumulated risk can be reduced at the expense of extending the coverage time. We show the effectiveness of this algorithm in extensive experiments.

AIJ Journal 2013 Journal Article

Teaching and leading an ad hoc teammate: Collaboration without pre-coordination

• Peter Stone
• Gal A. Kaminka
• Sarit Kraus
• Jeffrey S. Rosenschein
• Noa Agmon

As autonomous agents proliferate in the real world, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. In such ad hoc team settings, team strategies cannot be developed a priori. Rather, an agent must be prepared to cooperate with many types of teammates: it must collaborate without pre-coordination. This article defines two aspects of collaboration in two-player teams, involving either simultaneous or sequential decision making. In both cases, the ad hoc agent is more knowledgeable of the environment, and attempts to influence the behavior of its teammate such that they will attain the optimal possible joint utility.

AAMAS Conference 2012 Conference Paper

Leading Ad Hoc Agents in Joint Action Settings with Multiple Teammates

• Noa Agmon
• Peter Stone

The growing use of autonomous agents in practice may require agents to cooperate as a team in situations where they have limited prior knowledge about one another, cannot communicate directly, or do not share the same world models. These situations raise the need to design \emph{ad hoc} team members, i. e. , agents that will be able to cooperate without coordination in order to reach an optimal team behavior. This paper considers the problem of leading $N$-agent teams by an agent toward their optimal joint utility, where the agents compute their next actions based only on their most recent observations of their teammates' actions. We show that compared to previous results in two-agent teams, in larger teams the agent might not be able to lead the team to the action with maximal joint utility, thus its optimal strategy is to lead the team to the best possible \emph{reachable} cycle of joint actions. We describe a graphical model of the problem and a polynomial time algorithm for solving it. We then consider other variations of the problem, including leading teams of agents where they base their actions on longer history of past observations, leading a team by more than one ad hoc agent, and leading a teammate while the ad hoc agent is uncertain of its behavior.

ICRA Conference 2012 Conference Paper

On coordination in practical multi-robot patrol

• Noa Agmon
• Chien-Liang Fok
• Yehuda Emaliah
• Peter Stone 0001
• Christine Julien 0001
• Sriram Vishwanath

Multi-robot patrol is a fundamental application of multi-robot systems. While much theoretical work exists providing an understanding of the optimal patrol strategy for teams of coordinated homogeneous robots, little work exists on building and evaluating the performance of such systems for real. In this paper, we evaluate the performance of multirobot patrol in a practical outdoor distributed robotic system, and evaluate the effect of different coordination schemes on the performance of the robotic team. The multi-robot patrol algorithms evaluated vary in the level of robot coordination: no coordination, loose coordination, and tight coordination. In addition, we evaluate versions of these algorithms that distribute state information-either individual state, or entire team state (global-view state). Our experiments show that while tight coordination is theoretically optimal, it is not practical in practice. Instead, uncoordinated patrol performs best in terms of average waypoint visitation frequency, though loosely coordinated patrol that shares only individual state performed best in terms of worst-case frequency. Both are significantly better than a loosely coordinated algorithm based on sharing global-view state. We respond to this discrepancy between theory and practice, caused primarily by robot heterogeneity, by extending the theory to account for such heterogeneity, and find that the new theory accounts for the empirical results.

AAMAS Conference 2012 Conference Paper

Role Selection in Ad Hoc Teamwork

• Katie Genter
• Noa Agmon
• Peter Stone

An ad hoc team setting is one in which teammates must work together to obtain a common goal, but without any prior agreement regarding how to work together. In this work we introduce a role-based approach for ad hoc teamwork, in which each teammate is inferred to be following a specialized role that accomplishes a specific task or exhibits a particular behavior. In such cases, the role an ad hoc agent should select depends both on its own capabilities and on the roles currently selected by other team members. We present methods for evaluating the influence of the ad hoc agent’s role selection on the team’s utility and we examine empirically how to choose the best suited method for role assignment in a complex environment. Finally, we show that an appropriate assignment method can be determined from a limited amount of data and used successfully in new tasks that the team has not encountered before.

AAAI Conference 2011 Conference Paper

Comparing Agents’ Success against People in Security Domains

• Raz Lin
• Sarit Kraus
• Noa Agmon
• Samuel Barrett
• Peter Stone

The interaction of people with autonomous agents has become increasingly prevalent. Some of these settings include security domains, where people can be characterized as uncooperative, hostile, manipulative, and tending to take advantage of the situation for their own needs. This makes it challenging to design proficient agents to interact with people in such environments. Evaluating the success of the agents automatically before evaluating them with people or deploying them could alleviate this challenge and result in better designed agents. In this paper we show how Peer Designed Agents (PDAs) – computer agents developed by human subjects – can be used as a method for evaluating autonomous agents in security domains. Such evaluation can reduce the effort and costs involved in evaluating autonomous agents interacting with people to validate their efficacy. Our experiments included more than 70 human subjects and 40 PDAs developed by students. The study provides empirical support that PDAs can be used to compare the proficiency of autonomous agents when matched with people in security domains.

AAAI Conference 2011 Conference Paper

Multiagent Patrol Generalized to Complex Environmental Conditions

• Noa Agmon
• Daniel Urieli
• Peter Stone

The problem of multiagent patrol has gained considerable attention during the past decade, with the immediate applicability of the problem being one of its main sources of interest. In this paper we concentrate on frequency-based patrol, in which the agents’ goal is to optimize a frequency criterion, namely, minimizing the time between visits to a set of interest points. We consider multiagent patrol in environments with complex environmental conditions that affect the cost of traveling from one point to another. For example, in marine environments, the travel time of ships depends on parameters such as wind, water currents, and waves. We demonstrate that in such environments there is a need to consider a new multiagent patrol strategy which divides the given area into parts in which more than one agent is active, for improving frequency. We show that in general graphs this problem is intractable, therefore we focus on simplified (yet realistic) cyclic graphs with possible inner edges. Although the problem remains generally intractable in such graphs, we provide a heuristic algorithm that is shown to significantly improve point-visit frequency compared to other patrol strategies. For evaluation of our work we used a custom developed ship simulator that realistically models ship movement constraints such as engine force and drag and reaction of the ship to environmental changes.

TCS Journal 2011 Journal Article

Of robot ants and elephants: A computational comparison

• Asaf Shiloni
• Noa Agmon
• Gal A. Kaminka

In the robotics community, there exist implicit assumptions concerning the computational capabilities of robots. Two computational classes of robots emerge as focal points of recent research: robot ants and robot elephants. Ants have poor memory and communication capabilities, but are able to communicate using pheromones, in effect, turning their work area into a shared memory. By comparison, elephants are computationally stronger, have large memory, and are equipped with strong sensing and communication capabilities. Unfortunately, not much is known about the relation between the capabilities of these models in terms of the tasks they can address. In this paper, we present formal models of both ants and elephants, and investigate if one dominates the other. We present two algorithms: AntEater, which allows elephant robots to execute ant algorithms and ElephantGun, which converts elephant algorithms–specified as Turing machines–into ant algorithms. By exploring the computational capabilities of these algorithms, we reach interesting conclusions regarding the computational power of both models.

AAAI Conference 2011 Conference Paper

Role-Based Ad Hoc Teamwork

• Katie Genter
• Noa Agmon
• Peter Stone

An ad hoc team setting is one in which teammates must work together to obtain a common goal, but without any prior agreement regarding how to work together. In this abstract we present a role-based approach for ad hoc teamwork, in which each teammate is inferred to be following a specialized role that accomplishes a specific task or exhibits a particular behavior. In such cases, the role an ad hoc agent should select depends both on its own capabilities and on the roles currently selected by the other team members. We present methods for evaluating the influence of the ad hoc agent’s role selection on the team’s utility and we examine empirically how to select the best suited method for role assignment in a complex environment. Finally, we show that an appropriate assignment method can be determined from a limited amount of data and used successfully in similar new tasks that the team has not encountered before.

AAMAS Conference 2011 Conference Paper

Ship Patrol: Multiagent Patrol under Complex Environmental Conditions

• Noa Agmon
• Daniel Urieli
• Peter Stone

In the problem of multiagent patrol, a team of agents is required to repeatedly visit a target area in order to monitor possible changes in state. The growing popularity of this problem comes mainly from its immediate applicability to a wide variety of domains. In this paper we concentrate on frequency-based patrol, in which the agents' goal is to optimize a frequency criterion, namely, minimizing the time between visits to a set of interest points. In situations with varying environmental conditions, the influence of changes in the conditions on the cost of travel may be immense. For example, in marine environments, the travel time of ships depends on parameters such as wind, water currents, and waves. Such environments raise the need to consider a new multiagent patrol strategy which divides the given area into regions in which more than one agent is active, for improving frequency. We prove that in general graphs this problem is intractable, therefore we focus on simplified (yet realistic) cyclic graphs with possible inner edges. Although the problem remains generally intractable in such graphs, we provide a heuristic algorithm that is shown to significantly improve point-visit frequency compared to other patrol strategies.

AAMAS Conference 2011 Conference Paper

Who Goes There? Selecting a Robot to Reach a Goal Using Social Regret

• Meytal Traub
• Gal A. Kaminka
• Noa Agmon

A common decision problem in multi-robot applications involves deciding on which robot, out of a group of N robots, should travel to a goal location, to carry out a task there. Trivially, this decision problem can be solved greedily, by selecting the robot with the shortest expected travel time. However, this ignores the inherent uncertainty in path traversal times; we may prefer a robot that is slower (but always takes the same time), over a robot that is expected to reach the goal faster, but on occasion takes a very long time to arrive. We make several contributions that address this challenge. First, we bring to bear economic decision-making theory, to distinguish between different selection policies, based on risk (risk averse, risk seeking, etc. ). Second, we introduce social regret (the difference between the actual travel time by the selected robot, and the hypothetical time of other robots) to augment decision-making in practice. Then, we carry out experiments in simulation and with real robots, to demonstrate the usefulness of the selection procedures under real-world settings, and find that travel-time distributions have repeating characteristics.

AAMAS Conference 2010 Conference Paper

On Events in Multi-Robot Patrol in Adversarial Environments

• Noa Agmon

The problem of multi-robot patrol in adversarial environments has been gaining considerable interest during the recent years. In this problem, a team of mobile robots is required to repeatedly visit some target area in order to detectpenetrations that are controlled by an adversary. Little hasbeen written so far on the nature of the event of penetration, and it is commonly assumed that the goal of the robots is todetect the penetration at any time during its occurrence. Inthis paper we offer a new definition of an event, with correlation to a utility function such that the detection of the eventby the robots in different stages of its occurrence grants therobots a different reward. The goal of the robots is, then, tomaximize their utility from detecting the event. We provide three different models of events, for which wedescribe algorithms for calculating the expected utility fromdetecting the event and discuss the how the model influencesthe optimality of the patrol algorithm. In the first and basicmodel, we assume that there exists a reward function suchthat detecting an event at different times grants the robotswith an associated reward. In the second model, the eventmight evolve during its occurrence, and this progression correlates to both different rewards and to growing probabilityof detection. Finally, we consider a general model, in whichthe event can be detected from distance, where the probability of detection depends both on the distance from therobot and on the current state of the event. Last, we discuss how the new event models presented in this paper setgrounds for handling the problem of patrol in heterogeneousenvironments, where parts of the perimeter could be moresensitive to occurrence of events.

IJCAI Conference 2009 Conference Paper

• Noa Agmon
• Sarit Kraus
• Gal A. Kaminka
• Vladimir Sadov

We study the problem of multi-robot perimeter patrol in adversarial environments, under uncertainty of adversarial behavior. The robots patrol around a closed area using a nondeterministic patrol algorithm. The adversary’s choice of penetration point depends on the knowledge it obtained on the patrolling algorithm and its weakness points. Previous work investigated full knowledge and zero knowledge adversaries, and the impact of their knowledge on the optimal algorithm for the robots. However, realistically the knowledge obtained by the adversary is neither zero nor full, and therefore it will have uncertainty in its choice of penetration points. This paper considers these cases, and offers several approaches to bounding the level of uncertainty of the adversary, and its influence on the optimal patrol algorithm. We provide theoretical results that justify these approaches, and empirical results that show the performance of the derived algorithms used by simulated robots working against humans playing the role of the adversary is several different settings.

AAMAS Conference 2009 Conference Paper

Of Robot Ants and Elephants

• Asaf Shiloni
• Noa Agmon
• Gal A. Kaminka

Investigations of multi-robot systems often make implicit assumptions concerning the computational capabilities of the robots. Despite the lack of explicit attention to the computational capabilities of robots, two computational classes of robots emerge as focal points of recent research: Robot Ants and robot Elephants. Ants have poor memory and communication capabilities, but are able to communicate using pheromones, in effect turning their work area into a shared memory. By comparison, elephants are computationally stronger, have large memory, and are equipped with strong sensing and communication capabilities. Unfortunately, not much is known about the relation between the capabilities of these models in terms of the tasks they can address. In this paper, we present formal models of both ants and elephants, and investigate if one dominates the other. We present two algorithms: AntEater, which allows elephant robots to execute ant algorithms; and ElephantGun, which converts elephant algorithms—specified as Turing machines—into ant algorithms. By exploring the computational capabilities of these algorithms, we reach interesting conclusions regarding the computational power of both models.

ICRA Conference 2008 Conference Paper

Multi-robot perimeter patrol in adversarial settings

• Noa Agmon
• Sarit Kraus
• Gal A. Kaminka

This paper considers the problem of multi-robot patrol around a closed area with the existence of an adversary attempting to penetrate into the area. In case the adversary knows the patrol scheme of the robots and the robots use a deterministic patrol algorithm, then in many cases it is possible to penetrate with probability 1. Therefore this paper considers a non-deterministic patrol scheme for the robots, such that their movement is characterized by a probability p. This patrol scheme allows reducing the probability of penetration, even under an assumption of a strong opponent that knows the patrol scheme. We offer an optimal polynomial-time algorithm for finding the probability p such that the minimal probability of penetration detection throughout the perimeter is maximized. We describe three robotic motion models, defined by the movement characteristics of the robots. The algorithm described herein is suitable for all three models.

AAMAS Conference 2008 Conference Paper

The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol

• Noa Agmon
• Vladimir Sadov
• Sarit Kraus
• Gal Kaminka

This paper considers the problem of multi-robot patrolling around a closed area, in the presence of an adversary trying to penetrate the area. Previous work on planning in similar adversarial environments addressed worst-case settings, in which the adversary has full knowledge of the defending robots. It was shown that non deterministic algorithms may be effectively used to maximize the chances of blocking such a full-knowledge opponent, and such algorithms guarantee a “lower bound” to the performance of the team. However, an open question remains as to the impact of the knowledge of the opponent on the performance of the robots. This paper explores this question in depth and provides theoretical results, supported by extensive experiments with 68 human subjects concerning the compatibility of algorithms to the extent of information possessed by the subjects. First, we analytically examine the case of a zero-knowledge opponent—a different extreme—and show that surprisingly, this seemingly best-case scenario (from the point of view of defending robots) is optimally addressed by a deterministic, non-randomizing patrol. Moreover, we show empirically that an optimal algorithm for the full-knowledge opponent fails miserably in this case. We then address the case in which the adversary gained partial information, propose the Combine algorithm that maximizes the expected probability of penetration detection along with minimizing the deviation between the probabilities of penetration detection along the perimeter, and support the performance of this algorithm in the experiments.

ICRA Conference 2007 Conference Paper

Multi-Robot Area Patrol under Frequency Constraints

• Yehuda Emaliah
• Noa Agmon
• Gal A. Kaminka

This paper discusses the problem of generating patrol paths for a team of mobile robots inside a designated target area. Patrolling requires an area to be visited repeatedly by the robot(s) in order to monitor its current state. First, we present frequency optimization criteria used for evaluation of patrol algorithms. We then present a patrol algorithm that guarantees maximal uniform frequency, i. e. , each point in the target area is covered at the same optimal frequency. This solution is based on finding a circular path that visits all points in the area, while taking into account terrain directionality and velocity constraints. Robots are positioned uniformly along this path, using a second algorithm. Moreover, the solution is guaranteed to be robust in the sense that uniform frequency of the patrol is achieved as long as at least one robot works properly.

ICRA Conference 2006 Conference Paper

Constructing Spanning Trees for Efficient Multi-robot Coverage

• Noa Agmon
• Noam Hazon
• Gal A. Kaminka

This paper discusses the problem of building efficient coverage paths for a team of robots. An efficient multirobot coverage algorithm should result in a coverage path for every robot, such that the union of all paths generates a full coverage of the terrain and the total coverage time is minimized. A method, underlying several coverage algorithms, suggests the use of spanning trees as base for creating coverage paths. Current studies assume that the spanning tree is given, and try to make the most out of the given configuration. However, overall performance of the coverage is heavily dependent on the given spanning tree. This paper tackles the open challenge of constructing a coverage spanning tree that minimizes the time to complete coverage. We argue that the choice of the initial spanning tree has far reaching consequences concerning the coverage time, and if the tree is constructed appropriately, it could considerably reduce the coverage time of the terrain. Therefore the problem studied here is finding spanning trees that would decrease the coverage time of the terrain when used as base for multi-robot coverage algorithms. The main contributions of this paper are twofold. First, it provides initial sound discussion and results concerning the construction of the tree as a crucial base for any efficient coverage algorithm. Second, it describes a polynomial-time tree construction algorithm that, as shown in extensive simulations, dramatically improves the coverage time even when used as a basis for a simple, inefficient, coverage algorithm

AAAI Conference 2005 Conference Paper

Team Member Reallocation via Tree Pruning

• Noa Agmon

This paper considers the task reallocation problem, where k agents are to be extracted from a coordinated group of N agents in order to perform a new task. The interaction between the team members and the cost associated with this interaction are represented by a weighted graph. Consider a group of N robots organized in a formation, the graph is the monitoring graph which represents the sensorial capabilities of the robots, i. e. , which robot can sense the other and at what cost. Following this example, the team member reallocation problem this paper deals with is the extraction of k robots from the group in order to acquire a new target, while minimizing the cost of the interaction of the remaining group. In general, the method proposed here shifts the utility from the team member itself to the interaction between the members, and calculates the reallocation according to this interaction utility. We found that this can be done optimally by a deterministic polynomial time algorithm under several constraints, the first constraint is that k = O(log N). We describe several other domains in which this method is applicable.

SODA Conference 2004 Conference Paper

Fault-tolerant gathering algorithms for autonomous mobile robots

• Noa Agmon
• David Peleg