Robust Assignment Using Redundant Robots on Transport Networks with Uncertain Travel Time

Simple item page
cam.issuedOnline2020-05-04
cam.orpheus.counter4
cam.orpheus.successWed May 13 08:53:21 BST 2020 - Embargo updated
dc.contributor.authorProrok, A
dc.contributor.orcidProrok, A [0000-0001-7313-5983]
dc.date.accessioned2020-04-08T23:30:24Z
dc.date.available2020-04-08T23:30:24Z
dc.date.issued2020
dc.description.abstractThis paper considers the problem of assigning mo- bile robots to goals on transport networks with uncertain and potentially correlated information about travel times. Our aim is to produce optimal assignments, such that the average waiting time at destinations is minimized. Since noisy travel time estimates result in sub-optimal assignments, we propose a method that offers robustness to uncertainty by making use of redundant robot assignments. However, solving the redundant assignment problem optimally is strongly NP-hard. Hence, we exploit structural properties of our mathematical problem formulation to propose a polynomial-time, near-optimal solution. We demonstrate that our problem can be reduced to minimizing a supermodular cost function subject to a matroid constraint. This allows us to develop a greedy assignment algorithm, for which we derive sub-optimality bounds. We demonstrate the effectiveness of our approach with simulations on transport networks with correlated uncertain edge costs and uncertain node positions that lead to noisy travel time estimates. Comparisons to benchmark algorithms show that our method performs near-optimally and significantly better than non-redundant assignment. Finally, our findings include results on the benefit of diversity and complementarity in redundant robot coalitions; these insights contribute towards providing resilience to uncertainty through targeted composition of robot coalitions.
dc.description.sponsorshipThis work was supported by ARL DCIST CRA W911NF- 17-2-0181, by the Centre for Digital Built Britain, under InnovateUK grant number RG96233, for the research project “Co-Evolving Built Environments and Mobile Autonomy for Future Transport and Mobility”, and by the Engineering and Physical Sciences Research Council (grant EP/S015493/1).
dc.identifier.doi10.17863/CAM.51301
dc.identifier.eissn1558-3783
dc.identifier.issn1545-5955
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/304217
dc.publisherInstitute of Electrical and Electronics Engineers (IEEE)
dc.publisher.urlhttp://dx.doi.org/10.1109/tase.2020.2986641
dc.rightsAll rights reserved
dc.subjectRobot kinematics
dc.subjectUncertainty
dc.subjectTask analysis
dc.subjectRedundancy
dc.subjectOptimization
dc.subjectRobot sensing systems
dc.subjectMultirobot systems
dc.subjectsubmodular optimization
dc.subjecttask assignment
dc.titleRobust Assignment Using Redundant Robots on Transport Networks with Uncertain Travel Time
dc.typeArticle
dcterms.dateAccepted2020-04-06
prism.endingPage2037
prism.issueIdentifier4
prism.publicationDate2020
prism.publicationNameIEEE Transactions on Automation Science and Engineering
prism.startingPage2025
prism.volume17
pubs.funder-project-idEngineering and Physical Sciences Research Council (EP/S015493/1)
rioxxterms.licenseref.startdate2020-10-01
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserved
rioxxterms.typeJournal Article/Review
rioxxterms.versionAM
rioxxterms.versionofrecord10.1109/TASE.2020.2986641
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
T_ASE_Redundant_Assignment_Apollo.pdf
Size:
1.4 MB
Format:
Adobe Portable Document Format
Description:
Accepted version
Licence
http://www.rioxx.net/licenses/all-rights-reserved
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DepositLicenceAgreementv2.1.pdf
Size:
150.9 KB
Format:
Adobe Portable Document Format
Download
Collections
Cambridge University Research Outputs