Redundant Robot Assignment on Graphs with Uncertain Edge Costs
| dc.contributor.author | Prorok, Amanda | |
| dc.contributor.editor | Correll, N | |
| dc.contributor.editor | Schwager, M | |
| dc.contributor.editor | Otte, M | |
| dc.contributor.orcid | Prorok, Amanda [0000-0001-7313-5983] | |
| dc.date.accessioned | 2018-09-08T06:35:21Z | |
| dc.date.available | 2018-09-08T06:35:21Z | |
| dc.date.issued | 2019-02-21 | |
| dc.description.abstract | We provide a framework for the assignment of multiple robots to goal locations, when robot travel times are uncertain. Our premise is that time is the most valuable asset in the system. Hence, we make use of redundant robots to counter the effect of uncertainty and minimize the average waiting time at destinations. We apply our framework to transport networks represented as graphs, and consider uncertainty in the edge costs (i.e., travel time). Since solving the redundant assignment problem is strongly NP-hard, we exploit structural properties of our problem to propose a polynomial-time solution with provable sub-optimality bounds. Our method uses distributive aggregate functions, which allow us to efficiently (i.e., incrementally) compute the effective cost of assigning redundant robots. Experimental results on random graphs show that the deployment of redundant robots through our method reduces waiting times at goal locations, when edge traversals are uncertain. | |
| dc.identifier.doi | 10.17863/CAM.27308 | |
| dc.identifier.isbn | 3030058158 | |
| dc.identifier.isbn | 978-3-030-05815-9 | |
| dc.identifier.uri | https://www.repository.cam.ac.uk/handle/1810/279940 | |
| dc.language | English | |
| dc.language.iso | en | |
| dc.publisher | Springer International Publishing | |
| dc.subject | cs.RO | |
| dc.subject | cs.RO | |
| dc.subject | cs.MA | |
| dc.title | Redundant Robot Assignment on Graphs with Uncertain Edge Costs | |
| dc.type | Book chapter | |
| dcterms.dateAccepted | 2018-08-07 | |
| dcterms.isPartOf | Distributed Autonomous Robotic Systems | |
| prism.edition | 1st | |
| prism.endingPage | 327 | |
| prism.number | 22 | |
| prism.publicationDate | 2019 | |
| prism.publicationName | Distributed Autonomous Robotic Systems | |
| prism.startingPage | 313 | |
| prism.volume | 9 | |
| rioxxterms.licenseref.startdate | 2019-02-21 | |
| rioxxterms.licenseref.uri | http://www.rioxx.net/licenses/all-rights-reserved | |
| rioxxterms.type | Book chapter | |
| rioxxterms.version | AM | |
| rioxxterms.versionofrecord | 10.1007/978-3-030-05816-6 |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- redundant_assignment.pdf
- Size:
- 722.76 KB
- Format:
- Adobe Portable Document Format
- Description:
- Accepted version
- Licence
- http://www.rioxx.net/licenses/all-rights-reserved
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- DepositLicenceAgreementv2.1.pdf
- Size:
- 150.9 KB
- Format:
- Adobe Portable Document Format