Abstract How to form effective coalitions is an important issue in multi-agent systems. Coalition Structure Generation ( $${{\mathsf {CSG}}}$$ CSG ) is a fundamental problem whose formalization can encompass various applications related to multi-agent cooperation. $${{\mathsf {CSG}}}$$ CSG involves partitioning a set of agents into coalitions such that the social surplus (i.e., the sum of the values of all coalitions) is maximized. In traditional $${\mathsf {CSG}}$$ CSG , we are guaranteed that all coalitions will be successfully established, that is, the attendance rate of each agent for joining any coalition is assumed to be 1.0. Having the real world in mind, however, it is natural to consider the uncertainty of agents’ availabilities, e.g., an agent might be available only two or three days a week because of his/her own schedule. Probabilistic Coalition Structure Generation ( $${{\mathsf {PCSG}}}$$ PCSG ) is an extension of $${\mathsf {CSG}}$$ CSG where the attendance type of each agent is considered. The aim of this problem is to find the optimal coalition structure which maximizes the sum of the expected values of all coalitions. In $${\mathsf {PCSG}}$$ PCSG , since finding the optimal coalition structure easily becomes intractable, it is important to consider approximation algorithms, i.e., to consider a trade-off between the quality of the returned solution and tractability. In this paper, a formal framework for $${\mathsf {PCSG}}$$ PCSG is introduced. Approximation algorithms for $${\mathsf {PCSG}}$$ PCSG called Bounded Approximation Algorithm based on Attendance Types ( $${{\mathsf {BAAAT}}}$$ BAAAT ) and Involved $${\mathsf {BAAAT}}$$ BAAAT ( $${{\mathsf {IBAAAT}}}$$ IBAAAT ) are then presented. We prove a priori bounds on the quality of the solution returned by $${\mathsf {BAAAT}}$$ BAAAT and $${\mathsf {IBAAAT}}$$ IBAAAT with respect to the optimum and perform experimental evaluations on a number of benchmarks.

This dissertation is a compilation of six research papers that are focused on three different topics summarized in the text.The first three papers address NP-hard problems arising in ad-hoc wireless communication discussed in Chapter 2. In general, the task is to broadcast a message in a given network of wireless devices while minimizing the power consumption.Problems in this category differ in requirements on the network connectivity, models of power consumption, and the ability of the devices to initiate a signal transmission.Some of the common features of these problems are that a device can simultaneously transmit a signal to all devices within its communication vicinity, and that a signal can travel from its originator to its recipient via multiple intermediate devices.The wireless networks are modeled and studied by means of graph theory.Solution techniques for these problems involve mainly methods of integer linear programming and inexact algorithms with or without performance guarantee.The next paper is focused on the problem of minimum broadcast time.Unlike the previous topic, the devices are in this problem supposed to send a signal to at most one neighbouring device at a time.The objective is to determine a sequence of signal transmission from a given set of source devices to the remaining ones, while minimizing the time needed for spreading the signal.Chapter 3 describes this problem in detail along with several related problems.The minimum broadcast time problem is also studied from the perspective of integer linear programming as well as the inexact algorithm perspective.Continuous relaxations of the ILP models help to evaluate the quality of the studied inexact methods.The stronger the model is, the more accurate assessment it provides.The last two papers are dedicated to problems belonging to path planning for multiple robots discussed in Chapter 4. In general, these problems involve a group of agents (robots) initially deployed in an environment.The task is to find a sequence of their moves so that they reach pre-defined destination locations while optimizing a given criterion such as minimum makespan or minimum total arrival time.The agents' movement must obey a set of given rules.An extension of the problem considers agents divided into two (or more) adversarial teams, where the teams have either symmetric or asymmetric objectives.After introducing the adversarial element, the problem of finding a winning strategy for a given team becomes PSPACE-hard, like many other two player games with alternating turns.

The Distributed Constraint Optimization Problem (DCOP) lies at the foundations of multiagent cooperation. With DCOPs, the optimization in distributed resource allocation problems is formalized using constraint optimization problems. The solvers for the problem are designed based on decentralized cooperative algorithms that are performed by multiple agents. In a conventional DCOP, a single objective is considered. The Multiple Objective Distributed Constraint Optimization Problem (MODCOP) is an extension of the DCOP framework, where agents cooperatively have to optimize simultaneously multiple objective functions. In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. However, such models do not capture the interests of each agent. On the other hand, in several practical problems, the share of each agent is important. Such shares are modeled as preference values of agents. This class of problems can be defined using the MODCOP on the preferences of agents. In particular, we define optimization problems based on leximin ordering and Asymmetric DCOPs (Leximin AMODCOPs). The leximin defines an ordering among vectors of objective values. In addition, Asymmetric DCOPs capture the preferences of agents. Because the optimization based on the leximin ordering improves the equality among the satisfied preferences of the agents, this class of problems is important. We propose several solution methods for Leximin AMODCOPs generalizing traditional operators into the operators on sorted objective vectors and leximin. The solution methods applied to the Leximin AMODCOPs are based on pseudo trees. Also, the investigated search methods employ the concept of boundaries of the sorted vectors.

Distributed Constraint Optimization Problem (DCOP) has been studied as a fundamental component of multiagent systems. With DCOPs, various applications on multiagent systems are formalized as constraint optimization problems where variables and functions are distributed among agents. Leximin AMODCOP has been proposed as a class of Multiple Objective DCOPs, where multiple objectives for individual agents are optimized based on the leximin operator. This problem also relates to Asymmetric DCOPs based on its the criteria of fairness among agents. Previous studies explore only Leximin AMODCOPs on constraint graphs limited to functions with unary or binary scopes. We address the Leximin AMODCOPs on factor graphs that directly represent n-ary functions. A dynamic programming method on factor graphs is investigated as an exact solution method. In addition, for relatively dense problems, we also investigate several approximate/inexact algorithms.

Much of the Distributed Constraint Satisfaction Problem (DisCSP) solving research has addressed cooperating agents, and privacy was frequently mentioned as a significant motivation of the decentralization. While privacy may have a role for cooperating agents, it is easier understood in the context of self-interested utility-based agents, and this is the situation considered here. With utility-based agents, the DisCSP framework can be extended to model privacy and satisfaction under the concept of utility. We introduce Utilitarian Distributed Constraint Satisfaction Problems (UDisCSP), an extension of the DisCSP that exploits the rewards for finding a solution and the costs for losing privacy as guidance for the utility-based agents. A parallel can be drawn between Partially Observable Markov Decision Processes (POMDPs) and the problems solved by individual agents for UDisCSPs. Common DisCSP solvers are extended to take into account the utility function. In these extensions we assume that the planning problem is further restricting the set of communication actions to only the ones available in the corresponding solver protocols. The solvers obtained propose the action to be performed in each situation, defining thereby the policy of the agents.

High-quality bilingual dictionaries are very useful, but such resources are rarely available for lower-density language pairs, especially for those that are closely related. Using a third language to link two other languages is a well-known solution and usually requires only two input bilingual dictionaries A-B and B-C to automatically induce the new one, A-C . This approach, however, has never been demonstrated to utilize the complete structures of the input bilingual dictionaries, and this is a key failing because the dropped meanings negatively influence the result. This article proposes a constraint approach to pivot-based dictionary induction where language A and C are closely related. We create constraints from language similarity and model the structures of the input dictionaries as a Boolean optimization problem, which is then formulated within the Weighted Partial Max-SAT framework, an extension of Boolean Satisfiability (SAT). All of the encoded CNF (Conjunctive Normal Form), the predominant input language of modern SAT/MAX-SAT solvers, formulas are evaluated by a solver to produce the target (output) bilingual dictionary. Moreover, we discuss alternative formalizations as a comparison study. We designed a tool that uses the Sat4j library as the default solver to implement our method and conducted an experiment in which the output bilingual dictionary achieved better quality than the baseline method.

DirectDemocracyP2P is an open source platform developed in JAVA and offering peer-to-peer and mobile ad hoc wireless communication capabilities. The platform offers an API supporting plugins, beside its main application: deliberative petition drives (aka citizens' initiatives with integrated argumentation) [1]. An authentication-by-reputation technique based on digital signatures and peer review [2], [3] is integrated into the platform via this main application. Each peer manages independently its database of items of interest. The items of interest are encapsulated as self-contained pieces of information and uniquely identifiable using a system of global identifiers (GIDs). Each GID consists of a combination of public keys with creation dates, or digest values. Communication is based on a combination of push and pull mechanisms. [1].

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 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 assume 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 n-th power of 2 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), 2k/n) 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.

We present resolvent-based learning as a new nogood learning method for a distributed constraint satisfaction algorithm. This method is based on a look-back technique in constraint satisfaction algorithms and can efficiently make effective nogoods. We combine the method with the asynchronous weak-commitment search algorithm (AWC) and evaluate the performance of the resultant algorithm on distributed 3-coloring problems and distributed 3SAT problems. As a result, we found that the resolvent-based learning works well compared to previous learning methods for distributed constraint satisfaction algorithms. We also found that the AWC with the resolvent-based learning is able to find a solution with fewer cycles than the distributed breakout algorithm, which was known to be the most efficient algorithm (in terms of cycles) for solving distributed constraint satisfaction problems.