Loading…

GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications

The use of multiagent systems (MASs) in real-world applications keeps increasing, and diffuses into new domains, thanks to technological advances, increased acceptance, and demanding productivity requirements. Being able to automate the generation of mission plans for MASs is critical for managing c...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2022-10, Vol.52 (10), p.10627-10638
Main Authors: Miloradovic, Branko, Curuklu, Baran, Ekstrom, Mikael, Papadopoulos, Alessandro Vittorio
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c429t-3a12dbe30a963592a767b36e7360dd11b6c2ea85e24d9e1c73af0eaf791f20a03
cites cdi_FETCH-LOGICAL-c429t-3a12dbe30a963592a767b36e7360dd11b6c2ea85e24d9e1c73af0eaf791f20a03
container_end_page 10638
container_issue 10
container_start_page 10627
container_title IEEE transactions on cybernetics
container_volume 52
creator Miloradovic, Branko
Curuklu, Baran
Ekstrom, Mikael
Papadopoulos, Alessandro Vittorio
description The use of multiagent systems (MASs) in real-world applications keeps increasing, and diffuses into new domains, thanks to technological advances, increased acceptance, and demanding productivity requirements. Being able to automate the generation of mission plans for MASs is critical for managing complex missions in realistic settings. In addition, finding the right level of abstraction to represent any generic MAS mission is important for being able to provide general solution to the automated planning problem. In this article, we show how a mission for heterogeneous MASs can be cast as an extension of the traveling salesperson problem (TSP), and we propose a mixed-integer linear programming formulation. In order to solve this problem, a genetic mission planner (GMP), with a local plan refinement algorithm, is proposed. In addition, the comparative evaluation of CPLEX and GMP is presented in terms of timing and optimality of the obtained solutions. The algorithms are benchmarked on a proposed set of different problem instances. The results show that, in the presence of timing constraints, GMP outperforms CPLEX in the majority of test instances.
doi_str_mv 10.1109/TCYB.2021.3070913
format article
fullrecord <record><control><sourceid>proquest_pubme</sourceid><recordid>TN_cdi_pubmed_primary_33983890</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>9430776</ieee_id><sourcerecordid>2528174691</sourcerecordid><originalsourceid>FETCH-LOGICAL-c429t-3a12dbe30a963592a767b36e7360dd11b6c2ea85e24d9e1c73af0eaf791f20a03</originalsourceid><addsrcrecordid>eNpdkUFr3DAQhUVJacImP6AUiiCXHrJbjWRLVm_bTbIpZEmgaaEnIdvjVMG2XMmm7L-vlt3sobpIjL43zJtHyHtgCwCmPz-tfn1dcMZhIZhiGsQbcsZBFnPOVX5yfEt1Si5ifGHpFKmki3fkVAhdiEKzM_Kw3jx-oUu6xh5HV9GNi9H5nj62tu8x0MYHeocjBv-cCD9Fupna0QVf-pF-38YRO7ochtZVdky6eE7eNraNeHG4Z-TH7c3T6m5-_7D-tlrez6uM63EuLPC6RMGsliLX3CqpSiFRCcnqGqCUFUdb5MizWiNUStiGoW2UhoYzy8SMXO37xr84TKUZguts2Bpvnbl2P5fGh2fT1b9NngkmE_5pjw_B_5kwjqZzscI2udyZMjznBahMpjXOyOV_6IufQp_MGK5AiqwAyBIFe6oKPsaAzXECYGaXj9nlY3b5mEM-SfPx0HkqO6yPitc0EvBhDzhEPH7r5EApKf4BVJmSnw</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2716348114</pqid></control><display><type>article</type><title>GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications</title><source>IEEE Electronic Library (IEL) Journals</source><creator>Miloradovic, Branko ; Curuklu, Baran ; Ekstrom, Mikael ; Papadopoulos, Alessandro Vittorio</creator><creatorcontrib>Miloradovic, Branko ; Curuklu, Baran ; Ekstrom, Mikael ; Papadopoulos, Alessandro Vittorio</creatorcontrib><description>The use of multiagent systems (MASs) in real-world applications keeps increasing, and diffuses into new domains, thanks to technological advances, increased acceptance, and demanding productivity requirements. Being able to automate the generation of mission plans for MASs is critical for managing complex missions in realistic settings. In addition, finding the right level of abstraction to represent any generic MAS mission is important for being able to provide general solution to the automated planning problem. In this article, we show how a mission for heterogeneous MASs can be cast as an extension of the traveling salesperson problem (TSP), and we propose a mixed-integer linear programming formulation. In order to solve this problem, a genetic mission planner (GMP), with a local plan refinement algorithm, is proposed. In addition, the comparative evaluation of CPLEX and GMP is presented in terms of timing and optimality of the obtained solutions. The algorithms are benchmarked on a proposed set of different problem instances. The results show that, in the presence of timing constraints, GMP outperforms CPLEX in the majority of test instances.</description><identifier>ISSN: 2168-2267</identifier><identifier>ISSN: 2168-2275</identifier><identifier>EISSN: 2168-2275</identifier><identifier>DOI: 10.1109/TCYB.2021.3070913</identifier><identifier>PMID: 33983890</identifier><identifier>CODEN: ITCEB8</identifier><language>eng</language><publisher>United States: IEEE</publisher><subject>Algorithms ; Automation ; Extended colored traveling salesperson problem (ECTSP) ; Extended Colored Traveling Salesperson Problem (ECTSP)Genetic Algorithm (GA)Multirobot Mission PlanningMultirobot Systems ; genetic algorithm (GA) ; Genetics ; Integer programming ; Linear programming ; Mixed integer ; Multiagent systems ; Multiple robots ; multirobot mission planning ; multirobot systems ; Optimization ; Planning ; Robots ; Task analysis ; Taxonomy ; Urban areas</subject><ispartof>IEEE transactions on cybernetics, 2022-10, Vol.52 (10), p.10627-10638</ispartof><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) 2022</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c429t-3a12dbe30a963592a767b36e7360dd11b6c2ea85e24d9e1c73af0eaf791f20a03</citedby><cites>FETCH-LOGICAL-c429t-3a12dbe30a963592a767b36e7360dd11b6c2ea85e24d9e1c73af0eaf791f20a03</cites><orcidid>0000-0002-1364-8127 ; 0000-0002-5832-5452 ; 0000-0002-9051-929X</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/9430776$$EHTML$$P50$$Gieee$$Hfree_for_read</linktohtml><link.rule.ids>230,314,780,784,885,27924,27925,54796</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/33983890$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink><backlink>$$Uhttps://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-54306$$DView record from Swedish Publication Index$$Hfree_for_read</backlink></links><search><creatorcontrib>Miloradovic, Branko</creatorcontrib><creatorcontrib>Curuklu, Baran</creatorcontrib><creatorcontrib>Ekstrom, Mikael</creatorcontrib><creatorcontrib>Papadopoulos, Alessandro Vittorio</creatorcontrib><title>GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications</title><title>IEEE transactions on cybernetics</title><addtitle>TCYB</addtitle><addtitle>IEEE Trans Cybern</addtitle><description>The use of multiagent systems (MASs) in real-world applications keeps increasing, and diffuses into new domains, thanks to technological advances, increased acceptance, and demanding productivity requirements. Being able to automate the generation of mission plans for MASs is critical for managing complex missions in realistic settings. In addition, finding the right level of abstraction to represent any generic MAS mission is important for being able to provide general solution to the automated planning problem. In this article, we show how a mission for heterogeneous MASs can be cast as an extension of the traveling salesperson problem (TSP), and we propose a mixed-integer linear programming formulation. In order to solve this problem, a genetic mission planner (GMP), with a local plan refinement algorithm, is proposed. In addition, the comparative evaluation of CPLEX and GMP is presented in terms of timing and optimality of the obtained solutions. The algorithms are benchmarked on a proposed set of different problem instances. The results show that, in the presence of timing constraints, GMP outperforms CPLEX in the majority of test instances.</description><subject>Algorithms</subject><subject>Automation</subject><subject>Extended colored traveling salesperson problem (ECTSP)</subject><subject>Extended Colored Traveling Salesperson Problem (ECTSP)Genetic Algorithm (GA)Multirobot Mission PlanningMultirobot Systems</subject><subject>genetic algorithm (GA)</subject><subject>Genetics</subject><subject>Integer programming</subject><subject>Linear programming</subject><subject>Mixed integer</subject><subject>Multiagent systems</subject><subject>Multiple robots</subject><subject>multirobot mission planning</subject><subject>multirobot systems</subject><subject>Optimization</subject><subject>Planning</subject><subject>Robots</subject><subject>Task analysis</subject><subject>Taxonomy</subject><subject>Urban areas</subject><issn>2168-2267</issn><issn>2168-2275</issn><issn>2168-2275</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><sourceid>ESBDL</sourceid><recordid>eNpdkUFr3DAQhUVJacImP6AUiiCXHrJbjWRLVm_bTbIpZEmgaaEnIdvjVMG2XMmm7L-vlt3sobpIjL43zJtHyHtgCwCmPz-tfn1dcMZhIZhiGsQbcsZBFnPOVX5yfEt1Si5ifGHpFKmki3fkVAhdiEKzM_Kw3jx-oUu6xh5HV9GNi9H5nj62tu8x0MYHeocjBv-cCD9Fupna0QVf-pF-38YRO7ochtZVdky6eE7eNraNeHG4Z-TH7c3T6m5-_7D-tlrez6uM63EuLPC6RMGsliLX3CqpSiFRCcnqGqCUFUdb5MizWiNUStiGoW2UhoYzy8SMXO37xr84TKUZguts2Bpvnbl2P5fGh2fT1b9NngkmE_5pjw_B_5kwjqZzscI2udyZMjznBahMpjXOyOV_6IufQp_MGK5AiqwAyBIFe6oKPsaAzXECYGaXj9nlY3b5mEM-SfPx0HkqO6yPitc0EvBhDzhEPH7r5EApKf4BVJmSnw</recordid><startdate>20221001</startdate><enddate>20221001</enddate><creator>Miloradovic, Branko</creator><creator>Curuklu, Baran</creator><creator>Ekstrom, Mikael</creator><creator>Papadopoulos, Alessandro Vittorio</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>ESBDL</scope><scope>RIA</scope><scope>RIE</scope><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>7TB</scope><scope>8FD</scope><scope>F28</scope><scope>FR3</scope><scope>H8D</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>7X8</scope><scope>ABGEM</scope><scope>ADTPV</scope><scope>AOWAS</scope><scope>D8T</scope><scope>DF7</scope><scope>ZZAVC</scope><orcidid>https://orcid.org/0000-0002-1364-8127</orcidid><orcidid>https://orcid.org/0000-0002-5832-5452</orcidid><orcidid>https://orcid.org/0000-0002-9051-929X</orcidid></search><sort><creationdate>20221001</creationdate><title>GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications</title><author>Miloradovic, Branko ; Curuklu, Baran ; Ekstrom, Mikael ; Papadopoulos, Alessandro Vittorio</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c429t-3a12dbe30a963592a767b36e7360dd11b6c2ea85e24d9e1c73af0eaf791f20a03</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Automation</topic><topic>Extended colored traveling salesperson problem (ECTSP)</topic><topic>Extended Colored Traveling Salesperson Problem (ECTSP)Genetic Algorithm (GA)Multirobot Mission PlanningMultirobot Systems</topic><topic>genetic algorithm (GA)</topic><topic>Genetics</topic><topic>Integer programming</topic><topic>Linear programming</topic><topic>Mixed integer</topic><topic>Multiagent systems</topic><topic>Multiple robots</topic><topic>multirobot mission planning</topic><topic>multirobot systems</topic><topic>Optimization</topic><topic>Planning</topic><topic>Robots</topic><topic>Task analysis</topic><topic>Taxonomy</topic><topic>Urban areas</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Miloradovic, Branko</creatorcontrib><creatorcontrib>Curuklu, Baran</creatorcontrib><creatorcontrib>Ekstrom, Mikael</creatorcontrib><creatorcontrib>Papadopoulos, Alessandro Vittorio</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE Xplore Open Access Journals</collection><collection>IEEE All-Society Periodicals Package (ASPP) Online</collection><collection>IEEE Electronic Library Online</collection><collection>PubMed</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>ANTE: Abstracts in New Technology &amp; Engineering</collection><collection>Engineering Research Database</collection><collection>Aerospace Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>MEDLINE - Academic</collection><collection>SWEPUB Mälardalens högskola full text</collection><collection>SwePub</collection><collection>SwePub Articles</collection><collection>SWEPUB Freely available online</collection><collection>SWEPUB Mälardalens högskola</collection><collection>SwePub Articles full text</collection><jtitle>IEEE transactions on cybernetics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Miloradovic, Branko</au><au>Curuklu, Baran</au><au>Ekstrom, Mikael</au><au>Papadopoulos, Alessandro Vittorio</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications</atitle><jtitle>IEEE transactions on cybernetics</jtitle><stitle>TCYB</stitle><addtitle>IEEE Trans Cybern</addtitle><date>2022-10-01</date><risdate>2022</risdate><volume>52</volume><issue>10</issue><spage>10627</spage><epage>10638</epage><pages>10627-10638</pages><issn>2168-2267</issn><issn>2168-2275</issn><eissn>2168-2275</eissn><coden>ITCEB8</coden><abstract>The use of multiagent systems (MASs) in real-world applications keeps increasing, and diffuses into new domains, thanks to technological advances, increased acceptance, and demanding productivity requirements. Being able to automate the generation of mission plans for MASs is critical for managing complex missions in realistic settings. In addition, finding the right level of abstraction to represent any generic MAS mission is important for being able to provide general solution to the automated planning problem. In this article, we show how a mission for heterogeneous MASs can be cast as an extension of the traveling salesperson problem (TSP), and we propose a mixed-integer linear programming formulation. In order to solve this problem, a genetic mission planner (GMP), with a local plan refinement algorithm, is proposed. In addition, the comparative evaluation of CPLEX and GMP is presented in terms of timing and optimality of the obtained solutions. The algorithms are benchmarked on a proposed set of different problem instances. The results show that, in the presence of timing constraints, GMP outperforms CPLEX in the majority of test instances.</abstract><cop>United States</cop><pub>IEEE</pub><pmid>33983890</pmid><doi>10.1109/TCYB.2021.3070913</doi><tpages>12</tpages><orcidid>https://orcid.org/0000-0002-1364-8127</orcidid><orcidid>https://orcid.org/0000-0002-5832-5452</orcidid><orcidid>https://orcid.org/0000-0002-9051-929X</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2168-2267
ispartof IEEE transactions on cybernetics, 2022-10, Vol.52 (10), p.10627-10638
issn 2168-2267
2168-2275
2168-2275
language eng
recordid cdi_pubmed_primary_33983890
source IEEE Electronic Library (IEL) Journals
subjects Algorithms
Automation
Extended colored traveling salesperson problem (ECTSP)
Extended Colored Traveling Salesperson Problem (ECTSP)Genetic Algorithm (GA)Multirobot Mission PlanningMultirobot Systems
genetic algorithm (GA)
Genetics
Integer programming
Linear programming
Mixed integer
Multiagent systems
Multiple robots
multirobot mission planning
multirobot systems
Optimization
Planning
Robots
Task analysis
Taxonomy
Urban areas
title GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T04%3A48%3A41IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_pubme&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=GMP:%20A%20Genetic%20Mission%20Planner%20for%20Heterogeneous%20Multirobot%20System%20Applications&rft.jtitle=IEEE%20transactions%20on%20cybernetics&rft.au=Miloradovic,%20Branko&rft.date=2022-10-01&rft.volume=52&rft.issue=10&rft.spage=10627&rft.epage=10638&rft.pages=10627-10638&rft.issn=2168-2267&rft.eissn=2168-2275&rft.coden=ITCEB8&rft_id=info:doi/10.1109/TCYB.2021.3070913&rft_dat=%3Cproquest_pubme%3E2528174691%3C/proquest_pubme%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c429t-3a12dbe30a963592a767b36e7360dd11b6c2ea85e24d9e1c73af0eaf791f20a03%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2716348114&rft_id=info:pmid/33983890&rft_ieee_id=9430776&rfr_iscdi=true