mdh.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Miloradović, Branko
Publications (4 of 4) Show all publications
Miloradović, B., Curuklu, B., Ekström, M. & Papadopoulos, A. (2020). A Genetic Algorithm Approach to Multi-Agent Mission Planning Problems. In: Parlier G.; Liberatore F.; Demange M. (Ed.), Operations Research and Enterprise Systems: (pp. 109-134). Springer, Cham
Open this publication in new window or tab >>A Genetic Algorithm Approach to Multi-Agent Mission Planning Problems
2020 (English)In: Operations Research and Enterprise Systems / [ed] Parlier G.; Liberatore F.; Demange M., Springer, Cham , 2020, p. 109-134Chapter in book (Other academic)
Abstract [en]

Multi-Agent Systems (MASs) have received great attention from scholars and engineers in different domains, including computer science and robotics. MASs try to solve complex and challenging problems (e.g., a mission) by dividing them into smaller problem instances (e.g., tasks) that are allocated to the individual autonomous entities (e.g., agents). By fulfilling their individual goals, they lead to the solution to the overall mission. A mission typically involves a large number of agents and tasks, as well as additional constraints, e.g., coming from the required equipment for completing a given task. Addressing such problem can be extremely complicated for the human operator, and several automated approaches fall short of scalability. This paper proposes a genetic algorithm for the automation of multi-agent mission planning. In particular, the contributions of this paper are threefold. First, the mission planning problem is cast into an Extended Colored Traveling Salesperson Problem (ECTSP), formulated as a mixed integer linear programming problem. Second, a precedence constraint reparation algorithm to allow the usage of common variation operators for ECTSP is developed. Finally, a new objective function minimizing the mission makespan for multi-agent mission planning problems is proposed.

Place, publisher, year, edition, pages
Springer, Cham, 2020
Keywords
Multi-Agent Systems, Multi-agent mission planning, Extended Colored Traveling Salesperson (ECTSP), Genetic algorithms
National Category
Engineering and Technology Computer Systems
Identifiers
urn:nbn:se:mdh:diva-46604 (URN)10.1007/978-3-030-37584-3_6 (DOI)2-s2.0-85076881781 (Scopus ID)978-3-030-37584-3 (ISBN)
Projects
Future factories in the CloudAggregate Farming in the Cloud
Available from: 2019-12-20 Created: 2019-12-20 Last updated: 2020-01-02Bibliographically approved
Frasheri, M., Miloradović, B., Curuklu, B., Ekström, M. & Papadopoulos, A. (2020). GLocal: A Hybrid Approach to the Multi-Agent Mission Re-Planning Problem.
Open this publication in new window or tab >>GLocal: A Hybrid Approach to the Multi-Agent Mission Re-Planning Problem
Show others...
2020 (English)Report (Other academic)
Abstract [en]

Multi-robot systems can be prone to failures during plan execution, depending on the harshness of the environment they are deployed in. As a consequence, initially devised plans may no longer be feasible, and a re-planning process needs to take place to re-allocate any pending tasks. Two main approaches emerge as possible solutions, a global re-planning technique using a centralized planner that will redo the task allocation with the updated world state information, or a decentralized approach that will focus on the local plan reparation, i.e., the re-allocation of those tasks initially assigned to the failed robots.The former approach produces an overall better solution, while the latter is less computationally expensive.The goal of this paper is to exploit the benefits of both approaches, while minimizing their drawbacks. To this end, we propose a hybrid approach {that combines a centralized planner with decentralized multi-agent planning}. In case of an agent failure, the local plan reparation algorithm tries to repair the plan through agent negotiation. If it fails to re-allocate all of the pending tasks, the global re-planning algorithm is invoked, which re-allocates all unfinished tasks from all agents.The hybrid approach was compared to planner approach, and it was shown that it improves on the makespan of a mission in presence of different numbers of failures,as a consequence of the local plan reparation algorithm.

Keywords
Multi-Agent Systems, Autonomous Agents, Centralized Planning, Decentralized Planning
National Category
Engineering and Technology Computer Systems
Identifiers
urn:nbn:se:mdh:diva-47902 (URN)
Available from: 2020-05-06 Created: 2020-05-06 Last updated: 2020-05-18Bibliographically approved
Miloradović, B., Curuklu, B., Ekström, M. & Papadopoulos, A. (2019). Extended colored traveling salesperson for modeling multi-agent mission planning problems. In: ICORES 2019 - Proceedings of the 8th International Conference on Operations Research and Enterprise Systems: . Paper presented at 8th International Conference on Operations Research and Enterprise Systems, ICORES 2019, 19 February 2019 through 21 February 2019 (pp. 237-244). SciTePress
Open this publication in new window or tab >>Extended colored traveling salesperson for modeling multi-agent mission planning problems
2019 (English)In: ICORES 2019 - Proceedings of the 8th International Conference on Operations Research and Enterprise Systems, SciTePress , 2019, p. 237-244Conference paper, Published paper (Refereed)
Abstract [en]

In recent years, multi-agent systems have been widely used in different missions, ranging from underwater to airborne. A mission typically involves a large number of agents and tasks, making it very hard for the human operator to create a good plan. A search for an optimal plan may take too long, and it is hard to make a time estimate of when the planner will finish. A Genetic algorithm based planner is proposed in order to overcome this issue. The contribution of this paper is threefold. First, an Integer Linear Programming (ILP) formulation of a novel Extensive Colored Traveling Salesperson Problem (ECTSP) is given. Second, a new objective function suitable for multi-agent mission planning problems is proposed. Finally, a reparation algorithm to allow usage of common variation operators for ECTSP has been developed. 

Place, publisher, year, edition, pages
SciTePress, 2019
Keywords
Colored traveling salesperson (CTSP), Genetic algorithms, Multi-agent mission planning, Integer programming, Operations research, Software agents, Human operator, Integer Linear Programming, Mission planning, Mission planning problem, Objective functions, Traveling salesperson problem, Variation operator, Multi agent systems
National Category
Computer Sciences
Identifiers
urn:nbn:se:mdh:diva-43305 (URN)2-s2.0-85064712559 (Scopus ID)9789897583520 (ISBN)
Conference
8th International Conference on Operations Research and Enterprise Systems, ICORES 2019, 19 February 2019 through 21 February 2019
Available from: 2019-05-09 Created: 2019-05-09 Last updated: 2019-10-01Bibliographically approved
Miloradović, B., Frasheri, M., Curuklu, B., Ekström, M. & Papadopoulos, A. (2019). TAMER: Task Allocation in Multi-robot Systems Through an Entity-Relationship Model. In: PRIMA 2019: Principles and Practice of Multi-Agent Systems. Paper presented at The 22nd International Conference on Principles and Practice of Multi-Agent Systems PRIMA'19, 28 Oct 2019, Turin, Italy (pp. 478-486).
Open this publication in new window or tab >>TAMER: Task Allocation in Multi-robot Systems Through an Entity-Relationship Model
Show others...
2019 (English)In: PRIMA 2019: Principles and Practice of Multi-Agent Systems, 2019, p. 478-486Conference paper, Published paper (Refereed)
Abstract [en]

Multi-robot task allocation (MRTA) problems have been studied extensively in the past decades. As a result, several classifications have been proposed in the literature targeting different aspects of MRTA, with often a few commonalities between them. The goal of this paper is twofold. First, a comprehensive overview of early work on existing MRTA taxonomies is provided, focusing on their differences and similarities. Second, the MRTA problem is modelled using an Entity-Relationship (ER) conceptual formalism to provide a structured representation of the most relevant aspects, including the ones proposed within previous taxonomies. Such representation has the advantage of (i) representing MRTA problems in a systematic way, (ii) providing a formalism that can be easily transformed into a software infrastructure, and (iii) setting the baseline for the definition of knowledge bases, that can be used for automated reasoning in MRTA problems.

National Category
Engineering and Technology Computer Systems
Identifiers
urn:nbn:se:mdh:diva-46316 (URN)10.1007/978-3-030-33792-6_32 (DOI)2-s2.0-85076411190 (Scopus ID)978-3-030-33791-9 (ISBN)
Conference
The 22nd International Conference on Principles and Practice of Multi-Agent Systems PRIMA'19, 28 Oct 2019, Turin, Italy
Projects
DPAC - Dependable Platforms for Autonomous systems and ControlUnicorn -Sustainable, peaceful and efficient robotic refuse handlingAggregate Farming in the Cloud
Available from: 2019-12-12 Created: 2019-12-12 Last updated: 2020-05-07Bibliographically approved
Organisations

Search in DiVA

Show all publications