@inproceedings {icaps16-11,
    track    = {​​Robotics Track},
    title    = {Evaluation of Auction-Based Multi-Robot Routing by Parallel Simulation},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/12850},
    author   = {Akihiro Kishimoto and  Kiyohito Nagano},
    abstract = {Auction methods are a promising approximation approach for distributed routing including multi-robot routing, where targets on a map need to be allocated to agents while satisfying a team objective. While many algorithms based on sequential single-item (SSI) auctions have been presented, they are currently evaluated by serial simulation where agents serially calculate their bids on a single machine. 

We consider a scenario where a bidding algorithm incurs significant computational overhead due to on-demand calculations of the shortest distances on a road map, 
and evaluate the bidding algorithm under parallel simulations where agents perform bid calculations simultaneously on a parallel machine. We reveal that the algorithm suffers from severe synchronization overhead ignored by serial simulation. We also present the broadcasting and speculation techniques to alleviate such synchronization overhead. 

Our empirical results on multi-robot routing variants show that both techniques improve the efficiency of parallelization, and speculation achieves more significant improvement.},
    keywords = {planning and coordination methods for multiple robots}
}

{"_id":"nCbuEmQ5FjL3fBvSo","bibbaseid":"kishimoto-nagano-evaluationofauctionbasedmultirobotroutingbyparallelsimulation","downloads":0,"creationDate":"2016-03-09T03:04:31.939Z","title":"Evaluation of Auction-Based Multi-Robot Routing by Parallel Simulation","author_short":["Kishimoto, A.","Nagano, K."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"​​Robotics Track","title":"Evaluation of Auction-Based Multi-Robot Routing by Parallel Simulation","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/12850","author":[{"firstnames":["Akihiro"],"propositions":[],"lastnames":["Kishimoto"],"suffixes":[]},{"firstnames":["Kiyohito"],"propositions":[],"lastnames":["Nagano"],"suffixes":[]}],"abstract":"Auction methods are a promising approximation approach for distributed routing including multi-robot routing, where targets on a map need to be allocated to agents while satisfying a team objective. While many algorithms based on sequential single-item (SSI) auctions have been presented, they are currently evaluated by serial simulation where agents serially calculate their bids on a single machine. We consider a scenario where a bidding algorithm incurs significant computational overhead due to on-demand calculations of the shortest distances on a road map, and evaluate the bidding algorithm under parallel simulations where agents perform bid calculations simultaneously on a parallel machine. We reveal that the algorithm suffers from severe synchronization overhead ignored by serial simulation. We also present the broadcasting and speculation techniques to alleviate such synchronization overhead. Our empirical results on multi-robot routing variants show that both techniques improve the efficiency of parallelization, and speculation achieves more significant improvement.","keywords":"planning and coordination methods for multiple robots","bibtex":"@inproceedings {icaps16-11,\r\n track = {​​Robotics Track},\r\n title = {Evaluation of Auction-Based Multi-Robot Routing by Parallel Simulation},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/12850},\r\n author = {Akihiro Kishimoto and Kiyohito Nagano},\r\n abstract = {Auction methods are a promising approximation approach for distributed routing including multi-robot routing, where targets on a map need to be allocated to agents while satisfying a team objective. While many algorithms based on sequential single-item (SSI) auctions have been presented, they are currently evaluated by serial simulation where agents serially calculate their bids on a single machine. \r\n\r\nWe consider a scenario where a bidding algorithm incurs significant computational overhead due to on-demand calculations of the shortest distances on a road map, \r\nand evaluate the bidding algorithm under parallel simulations where agents perform bid calculations simultaneously on a parallel machine. We reveal that the algorithm suffers from severe synchronization overhead ignored by serial simulation. We also present the broadcasting and speculation techniques to alleviate such synchronization overhead. \r\n\r\nOur empirical results on multi-robot routing variants show that both techniques improve the efficiency of parallelization, and speculation achieves more significant improvement.},\r\n keywords = {planning and coordination methods for multiple robots}\r\n}\r\n\r\n","author_short":["Kishimoto, A.","Nagano, K."],"key":"icaps16-11","id":"icaps16-11","bibbaseid":"kishimoto-nagano-evaluationofauctionbasedmultirobotroutingbyparallelsimulation","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/12850"},"keyword":["planning and coordination methods for multiple robots"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"search_terms":["evaluation","auction","based","multi","robot","routing","parallel","simulation","kishimoto","nagano"],"keywords":["planning and coordination methods for multiple robots"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}