The Experts below are selected from a list of 16101 Experts worldwide ranked by ideXlab platform

Lovekesh Vig - One of the best experts on this subject based on the ideXlab platform.

  • Non-additive multi-objective robot Coalition Formation
    Expert Systems with Applications, 2014
    Co-Authors: Manoj Agarwal, Naveen Kumar, Lovekesh Vig
    Abstract:

    Manifold increase in the complexity of robotic tasks has mandated the use of robotic teams called Coalitions that collaborate to perform complex tasks. In this scenario, the problem of allocating tasks to teams of robots (also known as the Coalition Formation problem) assumes significance. So far, solutions to this NP-hard problem have focused on optimizing a single utility function such as resource utilization or the number of tasks completed. We have modeled the multi-robot Coalition Formation problem as a multi-objective optimization problem with conflicting objectives. This paper extends our recent work in multi-objective approaches to robot Coalition Formation, and proposes the application of the Pareto Archived Evolution Strategy (PAES) algorithm to the Coalition Formation problem, resulting in more efficient solutions. Simulations were carried out to demonstrate the relative diversity in the solution sets generated by PAES as compared to previously studied methods. Experiments also demonstrate the relative scalability of PAES. Finally, three different selection strategies were implemented to choose solutions from the Pareto optimal set. Impact of the selection strategies on the final Coalitions formed has been shown using Player/Stage.

  • Coalition Formation: From Software Agents to Robots
    Journal of Intelligent and Robotic Systems, 2007
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    A problem that has recently attracted the attention of the research community is the autonomous Formation of robot teams to perform complex multi-robot tasks. The corresponding problem for software agents is also known in the multi-agent community as the Coalition Formation problem. Numerous algorithms for software agent Coalition Formation have been provided that allow for efficient cooperation in both competitive and cooperative environments. However, despite the plethora of relevant literature on the software agent Coalition Formation problem, and the existence of similar problems in theoretical computer science, the multi-robot Coalition Formation problem has not been sufficiently grounded for different tasks and task environments. In this paper, comparisons are drawn to highlight the differences between software agents and robotics, and parallel problems from theoretical computer science are identified. This paper further explores robot Coalition Formation in different practical robotic environments. A heuristic-based Coalition Formation algorithm from our previous work was extended to operate in precedence ordered cooperative environments. In order to explore Coalition Formation in competitive environments, the paper also studies the RACHNA system, a market based Coalition Formation system. Finally, the paper investigates the notion of task preemption for complex multi-robot tasks in random allocation environments.

  • Multi-robot Coalition Formation
    IEEE Transactions on Robotics, 2006
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    As the community strives towards autonomous multi- robot systems, there is a need for these systems to autonomously form Coalitions to complete assigned missions. Numerous Coalition Formation algorithms have been proposed in the software agent lit- erature. Algorithms exist that form agent Coalitions in both super additive and non-super additive environments. The algorithmic techniques vary from negotiation-based protocols in multi-agent system (MAS) environments to those based on computation in distributed problem solving (DPS) environments. Coalition for- mation behaviors have also been discussed in relation to game theory. Despite the plethora ofMASCoalition Formation literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multi-robot system. There exists a discrepancy between the multi-agent algorithms and their applicability to the multi-robot domain. This paper aims to bridge that discrepancy by unearthing the issues that arise while attempting to tailor these algorithms to the multi-robot domain. A well-known multi-agent Coalition Formation algorithm has been studied in order to identify the necessary modifications to facili- tate its application to the multi-robot domain. This paper reports multi-robot Coalition Formation results based upon simulation and actual robot experiments. A multi-agent Coalition Formation algorithm has been demonstrated on an actual robot system

  • Multi-Robot Coalition Formation (REGULAR PAPER)
    2005
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    As the community strives towards autonomous multi-robot systems, there is a need for these systems to autonomously form Coalitions to complete assigned missions. Numerous Coalition Formation algorithms have been proposed in the software agent literature. Algorithms exist that form agent Coalitions in both super additive and non-super additive environments. The algorithmic techniques vary from negotiation-based protocols in Multi-Agent System (MAS) environments to those based on computation in Distributed Problem Solving (DPS) environments. Coalition Formation behaviors have also been discussed in relation to game theory. Despite the plethora of MAS Coalition Formation literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multi-robot system. There exists a discrepancy between the multi-agent algorithms and their applicability to the multi-robot domain. This paper aims to bridge that discrepancy by unearthing the issues that arise while attempting to tailor these algorithms to the multi-robot domain. A well-known multi-agent Coalition Formation algorithm has been studied in order to identify the necessary modifications to facilitate its application to the multi-robot domain. This paper reports multi-robot Coalition Formation results based upon simulation and actual robot experiments. A multi-agent Coalition Formation algorithm has been demonstrated on an actual robot system.

  • IICAI - A Framework for Multi-Robot Coalition Formation.
    2005
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    Task allocation is a fundamental problem that any multirobot system must address. Numerous multi-robot task allocation schemes have been proposed over the past decade. A vast majority of these schemes address the problem of assigning a single robot to each task. However as the complexity of multi-robot tasks increases, often situations arise where multiple robot teams need to be assigned to a set of tasks. This problem, also known as the Coalition Formation problem has received relatively little attention in the multi-robot community. This paper provides a generic, task independent framework for solutions to this problem for a variety task environments. In particular, the paper introduces RACHNA, a novel auction based Coalition Formation system for dynamic task environments. This is an extension to our previous work which proposed a static multi-robot Coalition Formation algorithm based on a popular heuristic from the Distributed Artificial Intelligence

Julie A. Adams - One of the best experts on this subject based on the ideXlab platform.

  • Coalition Formation: From Software Agents to Robots
    Journal of Intelligent and Robotic Systems, 2007
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    A problem that has recently attracted the attention of the research community is the autonomous Formation of robot teams to perform complex multi-robot tasks. The corresponding problem for software agents is also known in the multi-agent community as the Coalition Formation problem. Numerous algorithms for software agent Coalition Formation have been provided that allow for efficient cooperation in both competitive and cooperative environments. However, despite the plethora of relevant literature on the software agent Coalition Formation problem, and the existence of similar problems in theoretical computer science, the multi-robot Coalition Formation problem has not been sufficiently grounded for different tasks and task environments. In this paper, comparisons are drawn to highlight the differences between software agents and robotics, and parallel problems from theoretical computer science are identified. This paper further explores robot Coalition Formation in different practical robotic environments. A heuristic-based Coalition Formation algorithm from our previous work was extended to operate in precedence ordered cooperative environments. In order to explore Coalition Formation in competitive environments, the paper also studies the RACHNA system, a market based Coalition Formation system. Finally, the paper investigates the notion of task preemption for complex multi-robot tasks in random allocation environments.

  • Multi-robot Coalition Formation
    IEEE Transactions on Robotics, 2006
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    As the community strives towards autonomous multi- robot systems, there is a need for these systems to autonomously form Coalitions to complete assigned missions. Numerous Coalition Formation algorithms have been proposed in the software agent lit- erature. Algorithms exist that form agent Coalitions in both super additive and non-super additive environments. The algorithmic techniques vary from negotiation-based protocols in multi-agent system (MAS) environments to those based on computation in distributed problem solving (DPS) environments. Coalition for- mation behaviors have also been discussed in relation to game theory. Despite the plethora ofMASCoalition Formation literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multi-robot system. There exists a discrepancy between the multi-agent algorithms and their applicability to the multi-robot domain. This paper aims to bridge that discrepancy by unearthing the issues that arise while attempting to tailor these algorithms to the multi-robot domain. A well-known multi-agent Coalition Formation algorithm has been studied in order to identify the necessary modifications to facili- tate its application to the multi-robot domain. This paper reports multi-robot Coalition Formation results based upon simulation and actual robot experiments. A multi-agent Coalition Formation algorithm has been demonstrated on an actual robot system

  • Multi-Robot Coalition Formation (REGULAR PAPER)
    2005
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    As the community strives towards autonomous multi-robot systems, there is a need for these systems to autonomously form Coalitions to complete assigned missions. Numerous Coalition Formation algorithms have been proposed in the software agent literature. Algorithms exist that form agent Coalitions in both super additive and non-super additive environments. The algorithmic techniques vary from negotiation-based protocols in Multi-Agent System (MAS) environments to those based on computation in Distributed Problem Solving (DPS) environments. Coalition Formation behaviors have also been discussed in relation to game theory. Despite the plethora of MAS Coalition Formation literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multi-robot system. There exists a discrepancy between the multi-agent algorithms and their applicability to the multi-robot domain. This paper aims to bridge that discrepancy by unearthing the issues that arise while attempting to tailor these algorithms to the multi-robot domain. A well-known multi-agent Coalition Formation algorithm has been studied in order to identify the necessary modifications to facilitate its application to the multi-robot domain. This paper reports multi-robot Coalition Formation results based upon simulation and actual robot experiments. A multi-agent Coalition Formation algorithm has been demonstrated on an actual robot system.

  • IICAI - A Framework for Multi-Robot Coalition Formation.
    2005
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    Task allocation is a fundamental problem that any multirobot system must address. Numerous multi-robot task allocation schemes have been proposed over the past decade. A vast majority of these schemes address the problem of assigning a single robot to each task. However as the complexity of multi-robot tasks increases, often situations arise where multiple robot teams need to be assigned to a set of tasks. This problem, also known as the Coalition Formation problem has received relatively little attention in the multi-robot community. This paper provides a generic, task independent framework for solutions to this problem for a variety task environments. In particular, the paper introduces RACHNA, a novel auction based Coalition Formation system for dynamic task environments. This is an extension to our previous work which proposed a static multi-robot Coalition Formation algorithm based on a popular heuristic from the Distributed Artificial Intelligence

  • Issues in Multi-Robot Coalition Formation
    Multi-Robot Systems. From Swarms to Intelligent Automata Volume III, 1
    Co-Authors: Lovekesh Vig, Julie A. Adams
    Abstract:

    Numerous Coalition Formation algorithms exist in the Distributed Artificial Intelligence literature. Algorithms exist that form agent Coalitions in both super additive and non-super additive environments. The employed techniques vary from negotiation-based protocols in Multi-Agent System (MAS) environments to those based on computation in Distributed Problem Solving (DPS) environments. Coalition Formation behaviors have also been discussed in the game theory literature.

Daijie Cheng - One of the best experts on this subject based on the ideXlab platform.

  • Algorithms for Transitive Dependence-Based Coalition Formation
    IEEE Transactions on Industrial Informatics, 2007
    Co-Authors: Zhiqi Shen, Chunyan Miao, Daijie Cheng
    Abstract:

    Coalition Formation methods allow autonomous agents to join together in order to act as a coherent group in which they increase their individual gains by collaborating with each other. Although there are some research efforts toward Coalition Formation in multiagent systems (MAS), such as game theory-based approaches, these methods cannot be easily applied in real-world scenarios. Based on a novel social reasoning theory, namely, transitive dependence theory, this work proposes two dynamic Coalition Formation algorithms for Coalition Formation: 1) without and-action dependence and 2) with and-action dependence, respectively. While most related work addresses the problem of searching for the optimal Coalition structure (CS), the proposed algorithms aim to find out the optimal Coalitions for specific goals. Theoretical analysis and experimental results suggest that 1) the algorithm for Coalition Formation without and-action dependence is of polynomial complexity and is efficient, and 2) when the incidence rate of and-action dependence is not high, the anytime algorithm for Coalition Formation with and-action dependence is also efficient although it has relatively high complexity (NP-complete).

  • A Coalition Formation Framework Based on Transitive Dependence
    IEICE Transactions on Information and Systems, 2005
    Co-Authors: Chunyan Miao, Daijie Cheng
    Abstract:

    Coalition Formation in multi-agent systems (MAS) is becoming increasingly important as it increases the ability of agents to execute tasks and maximize their payoffs. Dependence relations are regarded as the foundation of Coalition Formation. This paper proposes a novel dependence theory namely transitive dependence theory for dynamic Coalition Formation in multi-agent systems. Transitive dependence is an extension of direct dependence that supports an agent's reasoning about other social members during Coalition Formation. Based on the proposed transitive dependence theory, a dynamic Coalition Formation framework has been worked out which includes inFormation gathering, transitive dependence based reasoning for Coalition partners search and Coalition resolution. The nested Coalitions and how to deal with incomplete knowledge while forming Coalitions are also discussed in the paper.

Samir Aknine - One of the best experts on this subject based on the ideXlab platform.

  • Preferences and Constraints for Agent Coalition Formation
    2013
    Co-Authors: Souhila Arib, Samir Aknine
    Abstract:

    In this paper, we tackle the problem of Coalition Formation in multi-agent systems. We detail a new Coalition Formation model that uses the constraints of the agents to guide their search for Coalitions and to derive their preferences in order to facilitate their negotiations. Our work focuses especially on agents which are self-interested and want to cooperate in executing actions in their plans. We propose a general framework for the Coalition Formation in which the constraints are used to form suitable Coalitions. We describe a procedure that transforms such constraints into a structured input which is used by the agents during their negotiations. Then, we present the method which enables the agents to select the partners that are most likely to be interested in sharing their actions. We detail this method and provide the results of its experimental evaluation.

  • IAT - Preferences and Constraints for Agent Coalition Formation
    2013 IEEE WIC ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT), 2013
    Co-Authors: Souhila Arib, Samir Aknine
    Abstract:

    In this paper, we tackle the problem of Coalition Formation in multi-agent systems. We detail a new Coalition Formation model that uses the constraints of the agents to guide their search for Coalitions and to derive their preferences in order to facilitate their negotiations. Our work focuses especially on agents which are self-interested and want to cooperate in executing actions in their plans. We propose a general framework for the Coalition Formation in which the constraints are used to form suitable Coalitions. We describe a procedure that transforms such constraints into a structured input which is used by the agents during their negotiations. Then, we present the method which enables the agents to select the partners that are most likely to be interested in sharing their actions. We detail this method and provide the results of its experimental evaluation.

  • A Plan Based Coalition Formation Model for Multi-agent Systems
    2011 IEEE WIC ACM International Conferences on Web Intelligence and Intelligent Agent Technology, 2011
    Co-Authors: Souhila Arib, Samir Aknine
    Abstract:

    This article addresses the Coalition Formation problem in a multi-agent context where agents plan their activities dynamically and use these plans to coordinate their actions and form suitable Coalitions. In most Coalition Formation methods, when negotiating their Coalitions the agents focus mainly on the immediate tasks to be executed, in order to decide which Coalitions to form. Agents relegate the negotiations of the Coalitions for their subsequent tasks to later stages of the coordination process. This paper deals with this issue and proposes a new Coalition Formation model which is based on two principles:1) it uses the plans of the agents to guide the search for the Coalitions to be formed and shows the significance of not only taking into account the immediate actions of the agents in the Coalition Formation process, 2) it analyzes the Coalition proposals already suggested by other agents in order to derive their intentions and thus facilitate the negotiations fort he Coalitions. First we analyse and develop the constraints that should be enforced on self-interested agents, in order to form suitable Coalitions which guarantee significant solution concepts. Then we detail our Coalition Formation mechanism.

  • Scalable Coalition Formation Method for Large-Scale Systems
    2007
    Co-Authors: Samir Aknine, Luciana Arantes
    Abstract:

    Coalition Formation (CF) is frequently used as an efficient solution for achieving goals through resource sharing and exchange. However, most existing Coalition Formation methods suppose a global view of the system or the existence of facilitators which manage this view. This assumption is clearly unsuitable for wide multi-agent systems. In this paper, we propose a scalable Coalition Formation method adapted for large-scale distributed systems. In our approach, every agent has a partial view of the system and can only communicate with the agents of its own view.

  • IAT - Scalable Coalition Formation Method for Large-Scale Systems
    2007 IEEE WIC ACM International Conference on Intelligent Agent Technology (IAT'07), 2007
    Co-Authors: Samir Aknine, Luciana Arantes
    Abstract:

    Coalition Formation (CF) is frequently used as an efficient solution for achieving goals through resource sharing and exchange. However, most existing Coalition Formation methods suppose a global view of the system or the existence of facilitators which manage this view. This assumption is clearly unsuitable for wide multi-agent systems. In this paper, we propose a scalable Coalition Formation method adapted for large-scale distributed systems. In our approach, every agent has a partial view of the system and can only communicate with the agents of its own view.

Onn Shehory - One of the best experts on this subject based on the ideXlab platform.

  • A Feasible and Practical Coalition Formation Mechanism: Leveraging Compromise and Task Relationships
    2006
    Co-Authors: Samir Aknine, Onn Shehory
    Abstract:

    Recent studies have shown that compromise may facilitate Coalition Formation and increase agent utilities. In this study we leverage on those results. We devise a novel Coalition Formation mechanism that enhances compromise. Our mechanism can utilize inFormation on task relationships to reduce Formation complexity. The suggested mechanism works well with both cardinal and ordinal task values. Via experiments we show that the use of the suggested compromise-based Coalition Formation mechanism provides significant savings in the computation and communication complexity of Coalition Formation. Our results also show that when inFormation on task relationships is used, the complexity of Coalition Formation is further reduced. We demonstrate successful use of the mechanism for collaborative inFormation filtering, where agents combine linguistic rules to analyze documents' contents.

  • Reaching Agreements for Coalition Formation through Derivation of Agents' Intentions
    2006
    Co-Authors: Samir Aknine, Onn Shehory
    Abstract:

    This paper addresses the Coalition Formation problem in multiagent systems. Although several Coalition Formation models exist today, Coalition Formation using these models remains costly. As a consequence, applying these models through several iterations when required becomes time-consuming. This paper proposes a new Coalition Formation mechanism (CFM) to reduce this execution cost. This mechanism is based on four principles: (1) the use of inFormation on task relationships so as to reduce the computational complexity of the Coalition Formation; (2) the exploitation of the Coalition proposals formulated by certain agents in order to derive their intentions, (this principle makes the search for solutions easier, which in turn may result in earlier consensus and agreements-the intention derivation process is performed on a new graph structure introduced in this paper); (3) the use of several strategies for propagating the proposals of the agents in the Coalition Formation process; and (4) the dynamic reorganization of previous Coalitions.

  • ECAI - Reaching Agreements for Coalition Formation through Derivation of Agents' Intentions
    2006
    Co-Authors: Samir Aknine, Onn Shehory
    Abstract:

    This paper addresses the Coalition Formation problem in multiagent systems. Although several Coalition Formation models exist today, Coalition Formation using these models remains costly. As a consequence, applying these models through several iterations when required becomes time-consuming. This paper proposes a new Coalition Formation mechanism (CFM) to reduce this execution cost. This mechanism is based on four principles: (1) the use of inFormation on task relationships so as to reduce the computational complexity of the Coalition Formation; (2) the exploitation of the Coalition proposals formulated by certain agents in order to derive their intentions, (this principle makes the search for solutions easier, which in turn may result in earlier consensus and agreements-the intention derivation process is performed on a new graph structure introduced in this paper); (3) the use of several strategies for propagating the proposals of the agents in the Coalition Formation process; and (4) the dynamic reorganization of previous Coalitions.

  • Coalition Formation: Concessions, Task Relationships and Complexity Reduction
    arXiv: Multiagent Systems, 2005
    Co-Authors: Samir Aknine, Onn Shehory
    Abstract:

    Solutions to the Coalition Formation problem commonly assume agent rationality and, correspondingly, utility maximization. This in turn may prevent agents from making compromises. As shown in recent studies, compromise may facilitate Coalition Formation and increase agent utilities. In this study we leverage on those new results. We devise a novel Coalition Formation mechanism that enhances compromise. Our mechanism can utilize inFormation on task dependencies to reduce Formation complexity. Further, it works well with both cardinal and ordinal task values. Via experiments we show that the use of the suggested compromise-based Coalition Formation mechanism provides significant savings in the computation and communication complexity of Coalition Formation. Our results also show that when inFormation on task dependencies is used, the complexity of Coalition Formation is further reduced. We demonstrate successful use of the mechanism for collaborative inFormation filtering, where agents combine linguistic rules to analyze documents' contents.

  • Coalition Formation: Towards Feasible Solutions
    Fundamenta Informaticae, 2004
    Co-Authors: Onn Shehory
    Abstract:

    Coalition Formation research in the last decade has produced an array of Coalition Formation mechanisms. Although these address a variety of environments and settings, they are usually inadequate for practical applications. The major limitations of the proposed mechanisms that render them inapplicable are a high computational complexity, and unrealistic assumptions regarding the availability of inFormation. In this article we present two recent Coalition Formation mechanisms that attempt to overcome these limitations. One of the mechanisms introduces a very low complexity, allowing scaling to thousands of agents, and the other mechanism does not assume complete inFormation. Rather, it assumes private, subjective and inaccurate valuation of Coalitions. These two mechanisms do not solve all of the problems present in the field, however they point at promising directions that might lead to fully applicable solutions in future research.