Loading…

Robot Coordination for Energy-Balanced Matching and Sequence Dispatch of Robots to Events

Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2015-05, Vol.64 (5), p.1416-1428
Main Authors: Lukic, Milan, Barnawi, Ahmed, Stojmenovic, Ivan
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-c289t-c084c4c04869b6525ad2e7241b669558236f049e19818b0fa1e03f488dbe69d3
cites cdi_FETCH-LOGICAL-c289t-c084c4c04869b6525ad2e7241b669558236f049e19818b0fa1e03f488dbe69d3
container_end_page 1428
container_issue 5
container_start_page 1416
container_title IEEE transactions on computers
container_volume 64
creator Lukic, Milan
Barnawi, Ahmed
Stojmenovic, Ivan
description Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is discovered by a sensor and reported to a robot. Here, we present novel algorithms aimed at overcoming the shortcomings of several existing solutions. We propose pairwise distance based matching algorithm (PDM) to eliminate long edges by pairwise exchanges between matching pairs. Our sequence dispatch algorithm (SQD) iteratively finds the closest event-robot pair, includes the event in dispatch schedule of the selected robot and updates its position accordingly. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energy-balanced variants are obtained. We also present generalizations which handle multiple visits and timing constraints. Our localized algorithm MAD is based on information mesh infrastructure and local auctions within the robot network for obtaining the optimal dispatch schedule for each robot. The simulations conducted confirm the advantages of our algorithms over other existing solutions in terms of average robot-event distance and lifetime.
doi_str_mv 10.1109/TC.2014.2329689
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1109_TC_2014_2329689</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>6827922</ieee_id><sourcerecordid>3759032331</sourcerecordid><originalsourceid>FETCH-LOGICAL-c289t-c084c4c04869b6525ad2e7241b669558236f049e19818b0fa1e03f488dbe69d3</originalsourceid><addsrcrecordid>eNo9kL1PwzAQxS0EEqUwM7BYYk57dhzXN0IoH1IREmRhspzEKamKXWwXqf89KUVMJ9393runR8glgwljgNOqnHBgYsJzjlLhERmxophliIU8JiMApjLMBZySsxhXACA54Ii8v_raJ1p6H9remdR7Rzsf6NzZsNxlt2ZtXGNb-mxS89G7JTWupW_2a2uHNb3r42Z_oL6jv0aRJk_n39aleE5OOrOO9uJvjkl1P6_Kx2zx8vBU3iyyhitMWQNKNKIBoSTWsuCFabmdccFqKbEoFM9lBwItQ8VUDZ1hFvJOKNXWVmKbj8n1wXYT_JAqJr3y2-CGj5pJRJCKcTVQ0wPVBB9jsJ3ehP7ThJ1moPf16arU-_r0X32D4uqg6K21_7RUfIac5z-C-2oa</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1699068128</pqid></control><display><type>article</type><title>Robot Coordination for Energy-Balanced Matching and Sequence Dispatch of Robots to Events</title><source>IEEE Xplore (Online service)</source><creator>Lukic, Milan ; Barnawi, Ahmed ; Stojmenovic, Ivan</creator><creatorcontrib>Lukic, Milan ; Barnawi, Ahmed ; Stojmenovic, Ivan</creatorcontrib><description>Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is discovered by a sensor and reported to a robot. Here, we present novel algorithms aimed at overcoming the shortcomings of several existing solutions. We propose pairwise distance based matching algorithm (PDM) to eliminate long edges by pairwise exchanges between matching pairs. Our sequence dispatch algorithm (SQD) iteratively finds the closest event-robot pair, includes the event in dispatch schedule of the selected robot and updates its position accordingly. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energy-balanced variants are obtained. We also present generalizations which handle multiple visits and timing constraints. Our localized algorithm MAD is based on information mesh infrastructure and local auctions within the robot network for obtaining the optimal dispatch schedule for each robot. The simulations conducted confirm the advantages of our algorithms over other existing solutions in terms of average robot-event distance and lifetime.</description><identifier>ISSN: 0018-9340</identifier><identifier>EISSN: 1557-9956</identifier><identifier>DOI: 10.1109/TC.2014.2329689</identifier><identifier>CODEN: ITCOB4</identifier><language>eng</language><publisher>New York: IEEE</publisher><subject>Algorithm design and analysis ; Algorithms ; Educational institutions ; Robot kinematics ; Robot sensing systems ; Robots ; Schedules ; Wireless sensor networks</subject><ispartof>IEEE transactions on computers, 2015-05, Vol.64 (5), p.1416-1428</ispartof><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) May 2015</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c289t-c084c4c04869b6525ad2e7241b669558236f049e19818b0fa1e03f488dbe69d3</citedby><cites>FETCH-LOGICAL-c289t-c084c4c04869b6525ad2e7241b669558236f049e19818b0fa1e03f488dbe69d3</cites><orcidid>0000-0002-3761-4175</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/6827922$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids></links><search><creatorcontrib>Lukic, Milan</creatorcontrib><creatorcontrib>Barnawi, Ahmed</creatorcontrib><creatorcontrib>Stojmenovic, Ivan</creatorcontrib><title>Robot Coordination for Energy-Balanced Matching and Sequence Dispatch of Robots to Events</title><title>IEEE transactions on computers</title><addtitle>TC</addtitle><description>Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is discovered by a sensor and reported to a robot. Here, we present novel algorithms aimed at overcoming the shortcomings of several existing solutions. We propose pairwise distance based matching algorithm (PDM) to eliminate long edges by pairwise exchanges between matching pairs. Our sequence dispatch algorithm (SQD) iteratively finds the closest event-robot pair, includes the event in dispatch schedule of the selected robot and updates its position accordingly. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energy-balanced variants are obtained. We also present generalizations which handle multiple visits and timing constraints. Our localized algorithm MAD is based on information mesh infrastructure and local auctions within the robot network for obtaining the optimal dispatch schedule for each robot. The simulations conducted confirm the advantages of our algorithms over other existing solutions in terms of average robot-event distance and lifetime.</description><subject>Algorithm design and analysis</subject><subject>Algorithms</subject><subject>Educational institutions</subject><subject>Robot kinematics</subject><subject>Robot sensing systems</subject><subject>Robots</subject><subject>Schedules</subject><subject>Wireless sensor networks</subject><issn>0018-9340</issn><issn>1557-9956</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNo9kL1PwzAQxS0EEqUwM7BYYk57dhzXN0IoH1IREmRhspzEKamKXWwXqf89KUVMJ9393runR8glgwljgNOqnHBgYsJzjlLhERmxophliIU8JiMApjLMBZySsxhXACA54Ii8v_raJ1p6H9remdR7Rzsf6NzZsNxlt2ZtXGNb-mxS89G7JTWupW_2a2uHNb3r42Z_oL6jv0aRJk_n39aleE5OOrOO9uJvjkl1P6_Kx2zx8vBU3iyyhitMWQNKNKIBoSTWsuCFabmdccFqKbEoFM9lBwItQ8VUDZ1hFvJOKNXWVmKbj8n1wXYT_JAqJr3y2-CGj5pJRJCKcTVQ0wPVBB9jsJ3ehP7ThJ1moPf16arU-_r0X32D4uqg6K21_7RUfIac5z-C-2oa</recordid><startdate>20150501</startdate><enddate>20150501</enddate><creator>Lukic, Milan</creator><creator>Barnawi, Ahmed</creator><creator>Stojmenovic, Ivan</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0002-3761-4175</orcidid></search><sort><creationdate>20150501</creationdate><title>Robot Coordination for Energy-Balanced Matching and Sequence Dispatch of Robots to Events</title><author>Lukic, Milan ; Barnawi, Ahmed ; Stojmenovic, Ivan</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c289t-c084c4c04869b6525ad2e7241b669558236f049e19818b0fa1e03f488dbe69d3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Algorithm design and analysis</topic><topic>Algorithms</topic><topic>Educational institutions</topic><topic>Robot kinematics</topic><topic>Robot sensing systems</topic><topic>Robots</topic><topic>Schedules</topic><topic>Wireless sensor networks</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Lukic, Milan</creatorcontrib><creatorcontrib>Barnawi, Ahmed</creatorcontrib><creatorcontrib>Stojmenovic, Ivan</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998-Present</collection><collection>IEEE Xplore</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>Technology Research 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><jtitle>IEEE transactions on computers</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lukic, Milan</au><au>Barnawi, Ahmed</au><au>Stojmenovic, Ivan</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Robot Coordination for Energy-Balanced Matching and Sequence Dispatch of Robots to Events</atitle><jtitle>IEEE transactions on computers</jtitle><stitle>TC</stitle><date>2015-05-01</date><risdate>2015</risdate><volume>64</volume><issue>5</issue><spage>1416</spage><epage>1428</epage><pages>1416-1428</pages><issn>0018-9340</issn><eissn>1557-9956</eissn><coden>ITCOB4</coden><abstract>Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is discovered by a sensor and reported to a robot. Here, we present novel algorithms aimed at overcoming the shortcomings of several existing solutions. We propose pairwise distance based matching algorithm (PDM) to eliminate long edges by pairwise exchanges between matching pairs. Our sequence dispatch algorithm (SQD) iteratively finds the closest event-robot pair, includes the event in dispatch schedule of the selected robot and updates its position accordingly. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energy-balanced variants are obtained. We also present generalizations which handle multiple visits and timing constraints. Our localized algorithm MAD is based on information mesh infrastructure and local auctions within the robot network for obtaining the optimal dispatch schedule for each robot. The simulations conducted confirm the advantages of our algorithms over other existing solutions in terms of average robot-event distance and lifetime.</abstract><cop>New York</cop><pub>IEEE</pub><doi>10.1109/TC.2014.2329689</doi><tpages>13</tpages><orcidid>https://orcid.org/0000-0002-3761-4175</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0018-9340
ispartof IEEE transactions on computers, 2015-05, Vol.64 (5), p.1416-1428
issn 0018-9340
1557-9956
language eng
recordid cdi_crossref_primary_10_1109_TC_2014_2329689
source IEEE Xplore (Online service)
subjects Algorithm design and analysis
Algorithms
Educational institutions
Robot kinematics
Robot sensing systems
Robots
Schedules
Wireless sensor networks
title Robot Coordination for Energy-Balanced Matching and Sequence Dispatch of Robots to Events
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-24T23%3A12%3A08IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Robot%20Coordination%20for%20Energy-Balanced%20Matching%20and%20Sequence%20Dispatch%20of%20Robots%20to%20Events&rft.jtitle=IEEE%20transactions%20on%20computers&rft.au=Lukic,%20Milan&rft.date=2015-05-01&rft.volume=64&rft.issue=5&rft.spage=1416&rft.epage=1428&rft.pages=1416-1428&rft.issn=0018-9340&rft.eissn=1557-9956&rft.coden=ITCOB4&rft_id=info:doi/10.1109/TC.2014.2329689&rft_dat=%3Cproquest_cross%3E3759032331%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c289t-c084c4c04869b6525ad2e7241b669558236f049e19818b0fa1e03f488dbe69d3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1699068128&rft_id=info:pmid/&rft_ieee_id=6827922&rfr_iscdi=true