Multi-robot coalition formation (MRCF) refers to the formation of robot coalitions against complex tasks requiring multiple robots for execution. Situations, where the robots have to participate in multiple coalitions over time due to a large number of tasks, are called Time-extended MRCF. While being NP-hard, time-extended MRCF also holds the possibility of resource deadlocks due to any cyclic hold-and-wait conditions among the coalitions. Existing schemes compromise on solution quality to form workable, deadlock-free coalitions through instantaneous or incremental allocations.

    Design/methodology/approach

    This paper presents an evolutionary algorithm (EA)-based task allocation framework for improved, deadlock-free solutions against time-extended MRCF. The framework simultaneously allocates multiple tasks, allowing the robots to participate in multiple coalitions within their schedule. A directed acyclic graph–based representation of robot plans is used for deadlock detection and avoidance.

    Findings

    Allowing the robots to participate in multiple coalitions within their schedule, significantly improves the allocation quality. The improved allocation quality of the EA is validated against two auction schemes inspired by the literature.

    Originality/value

    To the best of the author's knowledge, this is the first framework which simultaneously considers multiple MR tasks for deadlock-free allocation while allowing the robots to participate in multiple coalitions within their plans.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Robot coalition formation against time-extended multi-robot tasks


    Weitere Titelangaben:

    Multi-robot coalition formation


    Beteiligte:


    Erscheinungsdatum :

    22.11.2022


    Format / Umfang :

    14 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Multi-robot Coalition Formation for Precision Agriculture Scenario Based on Gazebo Simulator

    Teslya, Nikolay / Smirnov, Alexander / Ionov, Artem et al. | TIBKAT | 2021


    A Framework for Cooperative Multi-Robot Surveillance Tasks

    Roman-Ballesteros, Isai / Pfeiffer, Carlos | IEEE | 2006


    Testing Maps for Robot Navigation Tasks

    Zhang, Longyuan | DataCite | 2024


    AERIAL ROBOT SYSTEM BASED ON MULTI-ROTOR FOR MECHANICAL TASKS

    LEE DONG JUN / NGUYEN HAI NGUYEN / LEE HO YONG | Europäisches Patentamt | 2016

    Freier Zugriff

    Collaborative Programming of Conditional Robot Tasks

    Willibald, Christoph / Eiband, Thomas / Lee, Dongheui | Deutsches Zentrum für Luft- und Raumfahrt (DLR) | 2020

    Freier Zugriff