Steven Okamoto

TIST Journal 2020 Journal Article

Market Clearing–based Dynamic Multi-agent Task Allocation

• Sofia Amador Nelke
• Steven Okamoto
• Roie Zivan

Realistic multi-agent team applications often feature dynamic environments with soft deadlines that penalize late execution of tasks. This puts a premium on quickly allocating tasks to agents. However, when such problems include temporal and spatial constraints that require tasks to be executed sequentially by agents, they are NP-hard, and thus are commonly solved using general and specifically designed incomplete heuristic algorithms. We propose FMC_TA, a novel such incomplete task allocation algorithm that allows tasks to be easily sequenced to yield high-quality solutions. FMC_TA first finds allocations that are fair (envy-free), balancing the load and sharing important tasks among agents, and efficient (Pareto optimal) in a simplified version of the problem. It computes such allocations in polynomial or pseudo-polynomial time (centrally or distributedly, respectively) using a Fisher market with agents as buyers and tasks as goods. It then heuristically schedules the allocations, taking into account inter-agent constraints on shared tasks. We empirically compare our algorithm to state-of-the-art incomplete methods, both centralized and distributed, on law enforcement problems inspired by real police logs. We present a novel formalization of the law enforcement problem, which we use to perform our empirical study. The results show a clear advantage for FMC_TA in total utility and in measures in which law enforcement authorities measure their own performance. Besides problems with realistic properties, the algorithms were compared on synthetic problems in which we increased the size of different elements of the problem to investigate the algorithm’s behavior when the problem scales. The domination of the proposed algorithm was found to be consistent.

JAAMAS Journal 2017 Journal Article

Balancing exploration and exploitation in incomplete Min/Max-sum inference for distributed constraint optimization

• Roie Zivan
• Tomer Parash
• Steven Okamoto

Abstract Distributed Constraint Optimization Problems (DCOPs) are NP-hard and therefore the number of studies that consider incomplete algorithms for solving them is growing. Specifically, the Max-sum algorithm has drawn attention in recent years and has been applied to a number of realistic applications. Unfortunately, in many cases Max-sum does not produce high-quality solutions. More specifically, Max-sum does not converge and explores solutions of low quality when run on problems whose constraint graph representation contains multiple cycles of different sizes. In this paper we advance the state-of-the-art in incomplete algorithms for DCOPs by: (1) proposing a version of the Max-sum algorithm that operates on an alternating directed acyclic graph (Max-sum_AD), which guarantees convergence in linear time; (2) solving a major weakness of Max-sum and Max-sum_AD that causes inconsistent costs/utilities to be propagated and affect the assignment selection, by introducing value propagation to Max-sum_AD (Max-sum_ADVP); and (3) proposing exploration heuristic methods that evidently improve the algorithms performance further. We prove that Max-sum_ADVP converges to monotonically improving states after each change of direction, and that it is guaranteed to converge in pseudo-polynomial time to a stable solution that does not change with further changes of direction. Our empirical study reveals a large improvement in the quality of the solutions produced by Max-sum_ADVP on various benchmarks, compared to the solutions produced by the standard Max-sum algorithm, Bounded Max-sum and Max-sum_AD with no value propagation. It is found to be the best guaranteed convergence inference algorithm for DCOPs. The exploration methods we propose for Max-sum_ADVP improve its performance further. However, anytime results demonstrate that their exploration level is not as efficient as a version of Max-sum, which uses Damping.

IJCAI Conference 2016 Conference Paper

Distributed Breakout: Beyond Satisfaction

• Steven Okamoto
• Roie Zivan
• Aviv Nahon

The Distributed Breakout Algorithm (DBA) is a local search algorithm that was originally designed to solve DisCSPs and DisMaxCSPs. Extending it to general-valued DCOPs requires three design choices: manner of modifying base costs (multiplicative weights or additive penalties); definition of constraint violation (non-zero cost, non-minimum cost, and maximum cost); and scope of modifying cost tables during breakout (entry, row, column, or table). We propose Generalized DBA (GDBA) to span the 24 combinations in the three dimensions. In our theoretical analysis we prove that some variants of GDBA are equivalent for certain problems, and prove that other variants may find suboptimal solutions even on tree topologies where DBA is complete. Our extensive empirical evaluation on various benchmarks shows that in practice, GDBA is capable of finding solutions of equal or significantly lower cost than alternative heuristic approaches (including DSA).

AAAI Conference 2014 Conference Paper

Dynamic Multi-Agent Task Allocation with Spatial and Temporal Constraints

• Sofia Amador
• Steven Okamoto
• Roie Zivan

Realistic multi-agent team applications often feature dynamic environments with soft deadlines that penalize late execution of tasks. This puts a premium on quickly allocating tasks to agents, but finding the optimal allocation is NP-hard due to temporal and spatial constraints that require tasks to be executed sequentially by agents. We propose FMC TA, a novel task allocation algorithm that allows tasks to be easily sequenced to yield high-quality solutions. FMC TA first finds allocations that are fair (envyfree), balancing the load and sharing important tasks between agents, and efficient (Pareto optimal) in a simplified version of the problem. It computes such allocations in polynomial or pseudo-polynomial time (centrally or distributedly, respectively) using a Fisher market with agents as buyers and tasks as goods. It then heuristically schedules the allocations, taking into account inter-agent constraints on shared tasks. We empirically compare our algorithm to state-of-the-art incomplete methods, both centralized and distributed, on law enforcement problems inspired by real police logs. The results show a clear advantage for FMC TA both in total utility and in other measures commonly used by law enforcement authorities.

AIJ Journal 2014 Journal Article

Explorative anytime local search for distributed constraint optimization

• Roie Zivan
• Steven Okamoto
• Hilla Peled

Distributed Constraint Optimization Problems (DCOPs) are an elegant model for representing and solving many realistic combinatorial problems that are distributed by nature. DCOPs are NP-hard and therefore many recent studies consider incomplete algorithms for solving them. Distributed local search algorithms, in which agents in the system hold value assignments to their variables and iteratively make decisions on whether to replace them, can be used for solving DCOPs. However, because of the differences between the global evaluation of a system's state and the private evaluation of states by agents, agents are unaware of the global best state that is explored by the algorithm. Previous attempts to use local search algorithms for solving DCOPs reported the state held by the system at the termination of the algorithm, which was not necessarily the (global) best state explored. A general framework that enhances distributed local search algorithms for DCOPs with the anytime property is proposed. The proposed framework makes use of a BFS-tree in order to accumulate the costs of the system's state during the algorithm's iterative performance and to propagate the detection of a new best state when it is found. The proposed framework does not require additional network load. Agents are required to hold a small (linear) additional space (beside the requirements of the algorithm in use). We further propose a set of increased exploration heuristics that exploit the proposed anytime framework. These exploration methods implement different approaches towards exploration. Our empirical study considers various scenarios including random, realistic, and structured problems. It reveals the advantage of the use of the proposed heuristics in the anytime framework over state-of-the-art local search algorithms.

SoCS Conference 2013 Conference Paper

Multi-Agent Path Finding for Self Interested Agents

• Zahy Bnaya
• Roni Stern
• Ariel Felner
• Roie Zivan
• Steven Okamoto

Multi-agent pathfinding (MAPF) deals with planning paths for individual agents such that a global cost function (e. g. , the sum of costs) is minimized while avoiding collisions between agents. Previous work proposed centralized or fully cooperative decentralized algorithms assuming that agents will follow paths assigned to them. When agents are {\em self-interested}, however, they are expected to follow a path only if they consider that path to be their most beneficial option. In this paper we propose the use of a taxation scheme to implicitly coordinate self-interested agents in MAPF. We propose several taxation schemes and compare them experimentally. We show that intelligent taxation schemes can result in a lower total cost than the non coordinated scheme even if we take into consideration both travel cost and the taxes paid by agents.

AAMAS Conference 2012 Conference Paper

Solving Non-Zero Sum Multiagent Network Flow Security Games with Attack Costs

• Steven Okamoto
• Noam Hazon
• Katia Sycara

Moving assets through a transportation network is a crucial challenge in hostile environments such as future battlefields where malicious adversaries have strong incentives to attack vulnerable patrols and supply convoys. Intelligent agents must balance network costs with the harm that can be inflicted by adversaries who are in turn acting rationally to maximize harm while trading off against their own costs to attack. Furthermore, agents must choose their strategies even without full knowledge of their adversaries' capabilities, costs, or incentives. In this paper we model this problem as a non-zero sum game between two players, a sender who chooses flows through the network and an adversary who chooses attacks on the network. We advance the state of the art by: (1) moving beyond the zero-sum games previously considered to non-zero sum games where the adversary incurs attack costs that are not incorporated into the payoff of the sender; (2) introducing a refinement of the Stackelberg equilibrium that is more appropriate to network security games than previous solution concepts; and (3) using Bayesian games where the sender is uncertain of the capabilities, payoffs, and costs of the adversary. We provide polynomial time algorithms for finding equilibria in each of these cases. We also show how our approach can be applied to games where there are multiple adversaries.

AAMAS Conference 2011 Conference Paper

Allocating Spatially Distributed Tasks in Large, Dynamic Robot Teams

• Steven Okamoto
• Nathan Brooks
• Sean Owens
• Katia Sycara
• Paul Scerri

For an interesting class of emerging applications, a large robot team will need to distributedly allocate many more tasks than there are robots, with dynamically appearing tasks and a limited ability to communicate. The LA-DCOP algorithm can conceptually handle both large-scale problems and multiple tasks per robot, but has key limitations when allocating spatially distributed tasks. In this paper, we extend LA-DCOP with several alternative acceptance rules for robots to determine whether to take on an additional task, given the interaction with the tasks it has already committed to. We show that these acceptance rules dramatically outperform a naive LA-DCOP implementation. In addition, we developed a technique that lets the robots use completely local knowledge to adjust their task acceptance criteria to get the best possible performance at a given communication bandwidth level.

AAAI Conference 2008 Conference Paper

The Impact of Vertical Specialization on Hierarchical Multi-Agent Systems

• Steven Okamoto

Hierarchies are one of the most common organizational structures observed in multi-agent systems. In this paper we study vertical specialization as a reason for hierarchical structures. In vertically specialized systems, more highly skilled agents are also more costly. By using less capable agents to initially process tasks and forwarding only exceptional tasks to more capable agents, such systems may be able to economize on the number of highly capable agents. The result is a hierarchical structure with least capable agents at the bottom. However, such a structure increases the delay in completing some tasks, because they must pass through multiple levels of control. Thus, vertical specialization presents a tradeoff between economizing on skilled agents and increasing task completion time. We find that for a wide range of settings, vertical specialization induces an optimal hierarchy of height at most three. This suggests that a multi-agent system designer interested in exploiting vertical specialization needs to use at most three levels of specialization in order to reap most of the benefits.

AAMAS Conference 2007 Conference Paper

Locating RF Emitters with Large UAV Teams

• Paul Scerri
• Robin Glinton
• Sean Owens
• Steven Okamoto
• Katia Sycara

AAMAS Conference 2006 Conference Paper

Toward an Understanding of the Impact of Personal Assistants on Human Organizations

• Steven Okamoto
• Paul Scerri
• Katia Sycara

AAMAS Conference 2005 Conference Paper

Allocating Tasks in Extreme Teams

• Paul Scerri
• Alessandro Farinelli
• Steven Okamoto
• Milind Tambe