Author name cluster

Toshihiro Matsui

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers

2 author rows

AAMAS Conference 2010 Conference Paper

A Quantified Distributed Constraint Optimization Problem

Toshihiro Matsui
Marius Silaghi
Katsutoshi Hirayama
Makoto Yokoo
Hiroshi Matsuo
Satomi Baba

In this paper, we propose a Quantified Distributed Constraint Optimization problem (QDCOP) that extends the framework of Distributed Constraint Optimization problems (DCOPs). DCOPs havebeen studied as a fundamental model of multi-agent cooperation. In traditional DCOPs, all agents cooperate to optimize the sum oftheir cost functions. However, in practical systems some agentsmay desire to select the value of their variables without cooperation. In special cases, such agents may take the values with theworst impact on the quality of the result reachable by the optimization process. We apply existential/universal quantifiers to distinctuncooperative variables. A universally quantified variable is leftunassigned by the optimization as the result has to hold when ittakes any value from its domain, while an existentially quantifiedvariable takes exactly one of its values for each context. Similar classes of problems have recently been studied as (Distributed)Quantified Constraint Problems, where the variables of the CSPhave quantifiers. All constraints should be satisfied independentlyof the value taken by universal variables. We propose a QDCOPthat applies the concept of game tree search to DCOP. If the original problem is a minimization problem, agents that own universallyquantified variables may intend to maximize the cost value in theworst case. Other agents normally intend to optimize the minimizing problems. Therefore, only the bounds, especially the upperbounds, of the optimal value are guaranteed. The purpose of thenew class of problems is to compute such bounds, as well as tocompute sub-optimal solutions. For the QDCOP, we also proposeseveral methods that are based on min-max/alpha-beta and ADOPTalgorithms.

PDF

AAAI Conference 2010 Conference Paper

Coalition Structure Generation based on Distributed Constraint Optimization

Suguru Ueda
Atsushi Iwasaki
Makoto Yokoo
Marius Silaghi
Katsutoshi Hirayama
Toshihiro Matsui

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure Generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a coalition structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i. e. , we assume that the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might imagine that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve O(2n ) DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w∗ + 1), k/⌊n/2⌋) of the optimal CS, where w∗ is the tree width of a constraint graph. When k = 1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.

PDF Details

AAMAS Conference 2010 Conference Paper

Cooperative Problem Solving against Adversary: Quantified Distributed Constraint Satisfaction Problem

Satomi Baba
Atsushi Iwasaki
Makoto Yokoo
Marius Silaghi
Katsutoshi Hirayama
Toshihiro Matsui

In this paper, we extend the traditional formalization ofa Distributed Constraint Satisfaction Problems (DisCSP)to a Quantified DisCSP. A Quantified DisCSP includes several universally quantifiedvariables, while all of the variables in a traditional DisCSP areexistentially quantified. A universally quantified variable represents a choice of the nature oran adversary. A Quantified DisCSP formalizes a situation where a team of agents istrying to make a robust plan against the nature or an adversary. In this paper, we present the formalization of such aQuantified DisCSP and develop an algorithm for solving it. This algorithm generalizes the asynchronous backtracking algorithmused for solving a DisCSP. In this algorithm, agents communicate a value assignment calleda good in addition to the nogood used inasynchronous backtracking. Interestingly, the procedures executed by an adversarial/cooperative agent for good/nogood are totally symmetrical. Furthermore, we develop a method for improving this basic algorithm. Experimental evaluation results illustrate that we observe an easy-hard-easy transition by changing the tightness of constraints, while very loose problem instances are relatively hard. Also, the modification of the basic algorithm is effective and can achieve about 25\% reduction of cycles for the hardest problem instances.

PDF

AAMAS Conference 2009 Conference Paper

Adaptive Price Update in Distributed Lagrangian Relaxation Protocol

Katsutoshi Hirayama
Toshihiro Matsui
Makoto Yokoo

Distributed Lagrangian Relaxation Protocol (DisLRP) has been proposed to solve a distributed combinatorial maximization problem called the Generalized Mutual Assignment Problem (GMAP). In DisLRP, when updating Lagrange multipliers (prices) of goods, the agents basically control their step length, which determines the degree of update, by a static rule. A merit of this updating rule is that since it is static, it is easy to implement even without a central control. Furthermore, if we choose this static rule appropriately, we have observed empirically that DisLRP converges to a state providing a good upper bound. However, it must be difﬁcult to devise such a good static rule for updating step length since it naturally depends on problem instances to be solved. On the other hand, in a centralized context, the Lagrangian relaxation approach has conventionally computed step length by exploiting the least upper bound obtained during the search and a lower bound obtained through preprocessing. In this paper, we achieve this approach in a distributed environment where no central control exists and name the resultant protocol Adaptive DisLRP (ADisLRP). The key ideas of this new protocol are to 1) compute global information with a spanning tree, 2) update step length simultaneously with a synchronization protocol, and 3) estimate lower bounds during the search. We also show the robustness of ADisLRP through experiments where we compared ADisLRP with the previous protocols on the critically hard benchmark instances.

PDF

AAMAS Conference 2009 Conference Paper

Directed Soft Arc Consistency in Pseudo Trees

Toshihiro Matsui
Marius Călin Silaghi
Katsutoshi Hirayama
Makoto Yokoo
Hirohsi Matsuo

We propose an efficient method that applies directed soft arc consistency to a Distributed Constraint Optimization Problem (DCOP) which is a fundamental framework of multi-agent systems. With DCOPs a multi-agent system is represented as a set of variables and a set of constraints/cost functions. We focus on DCOP solvers that employ pseudo-trees. A pseudo-tree is a graph structure for a constraint network that represents a partial ordering of variables. Most pseudo-tree-based search algorithms perform optimistic searches using explicit/implicit backtracking in parallel. However, for cost functions taking a wide range of cost values, such exact algorithms require many search iterations, even if the constraint density is relatively low. Therefore additional improvements are necessary to reduce the search process. A previous study used a dynamic programming-based preprocessing technique that estimates the lower bound values of costs. However, there are opportunities for further improvements of efficiency. In addition, modifications of the search algorithm are necessary to use the estimated lower bounds. The proposed method applies soft arc consistency (soft AC) enforcement to DCOP. In the proposed method, directed soft AC is performed based on a pseudo-tree in a bottom up manner. Using the directed soft AC, the global lower bound value of cost functions is passed up to the root node of the pseudo-tree. The value of each cost function is also reduced. As a result, the original problem is converted to an equivalent problem which is efficiently solved using common search algorithms. The performance of the proposed method is evaluated by experimentation. The results show that it is more efficient than previous methods that estimate the lower bound of costs. Moreover, the proposed method is efficient for approximation algorithms that use bounded errors.

PDF

AAMAS Conference 2008 Conference Paper

Resource constrained distributed constraint optimization using resource constraint free pseudo-tree

Toshihiro Matsui
Marius Silaghi
Katsutoshi Hirayama
Makoto Yokoo
Hiroshi Matsuo

The Distributed Constraint Optimization Problem (DCOP) is a fundamental formalism for multi-agent cooperation. A dedicated framework called Resource Constrained DCOP (RCDCOP) has recently been proposed. RCDCOP models objective functions and resource constraints separately. A resource constraint is an n-ary constraint that represents the limit on the number of resources of a given type available to agents. Previous research addressing RCDCOPs employs the Adopt algorithm, which is a basic solver for DCOPs. In this paper we propose another version of the Adopt algorithm for RCDCOP using a pseudo-tree that is generated ignoring resource constraints. The key ideas of our work are as follows: (i) The pseudo-tree is generated ignoring resource constraints. (ii) Virtual variables are introduced, representing the usage of resources. These virtual variables are used to share resources among subtrees. These ideas are used to extend Adopt. The proposed method reduces the previous limitations in the construction of RCDCOP pseudo-trees. The efficiency of our technique depends on the class of problems being considered, and we describe the obtained experimental results.

PDF

AAAI Conference 2008 Conference Paper

Resource Constrained Distributed Constraint Optimization with Virtual Variables

Toshihiro Matsui
Katsutoshi Hirayama

Cooperative problem solving with resource constraints are important in practical multi-agent systems. Resource constraints are necessary to handle practical problems including distributed task scheduling with limited resource availability. A dedicated framework called Resource Constrained DCOP (RCDCOP) has recently been proposed. RCDCOP models objective functions and resource constraints separately. A resource constraint is an n-ary constraint that represents the limit on the number of resources of a given type available to agents. Previous research addressing RCDCOPs employs the Adopt algorithm, which is an efficient solver for DCOPs. An important graph structure for Adopt is the pseudo-tree for constraint networks. A pseudo-tree implies a partial ordering of variables. In this variable ordering, n-ary constrained variables are placed on a single path of the tree. Therefore, resource constraints that have large arity augment the depth of the pseudo-tree. This also reduces the parallelism, and therefore the efficiency of Adopt. In this paper we propose another version of the Adopt algorithm for RCDCOP using a pseudo-tree that is generated ignoring resource constraints. The proposed method reduces the previous limitations in the construction of RCDCOP pseudo-trees. The key ideas of our work are as follows: (i) The pseudo-tree is generated ignoring resource constraints. (ii) Virtual variables are introduced, representing the usage of resources. These virtual variables are used to share resources among sub-trees. However, the addition of virtual variables increases the search space. To handle this problem, influence of placement of virtual variables/resources constraints in the pseudo tree is considered. Moreover the search is pruned using the bounds defined by the resource constraints if possible. These ideas are used to extend Adopt. The efficiency of our technique depends on the class of problems being considered, and we describe the obtained experimental results.

PDF Details

ICRA Conference 2006 Conference Paper

Home Robot Service by Ceiling Ultrasonic Locator and Microphone Array

Satoshi Kagami
Simon Thompson 0002
Yoshifumi Nishida
Tadashi Enomoto
Toshihiro Matsui

This paper describes a mobile robot for home service purpose together with ceiling attached ultrasonic locator and microphone array. User call can be detected by those ceiling devices and then mobile robot navigates toward given location. After reaching to the given location, the robot tries to find out user location by using stereo camera, laser and triconcentric microphone array. We implemented those system at our experimental house "Rokko Holone". System components and experimental results are shown