The +1 Method Model-Free Adaptive Repositioning Policies for Robotic Multi-Agent Systems

The +1 Method Model-Free Adaptive Repositioning Policies for Robotic Multi-Agent Systems. Ruch, Claudio; Gächter, Joel; Hakenberg, Jan; Frazzoli, E. 2019.

Website abstract bibtex

Robotic multi-agent systems can efficiently handle spatially distributed tasks in dynamic environments. Problem instances of particular interest and generality are the dynamic vehicle routing problem and the dynamic traveling repairman problem. Operational policies for robotic fleets solving these two problems take decisions in an online setting with continuously arriving dynamic demands to optimize system time and efficiency. They can be classified along several lines. First, some require a model of the demand, e.g., based on historical information, while others work model-free. Second, they are designed for different operating conditions from light to heavy system load. Third, they work in a time-invariant or time-varying setting. We present a novel class of model-free operational policies for time-varying demands, with performance independent of the load factor and applicable to any number of dimensions, a combination of properties not achieved by any other operational policy in the literature. The underlying principle of the introduced policies is to send available robots to recent realizations of the stochastic process that generates service requests. In simple terms, the strategies rely on sending more than one robot for every service request arriving to the system. This leads to an advantage in scenarios where demand is non-uniformly distributed and correlated in space an time. We provide theoretical stability and performance guarantees for both the time-invariant and the time-varying cases as well as for correlated demand. We verify our theoretical results numerically. Finally, we apply our operational policy to the problem of mobility-on-demand fleet operation and demonstrate that it outperforms model-based and complex algorithms

@unpublished{
 title = {The +1 Method Model-Free Adaptive Repositioning Policies for Robotic Multi-Agent Systems},
 type = {unpublished},
 year = {2019},
 source = {ETH Zürich Research Colllection},
 identifiers = {[object Object]},
 keywords = {Anticipative Repositioning,Autonomous Mobility-on-Demand,Dispatching,Dynamic Traveling Repairman Problem,Dynamic Vehicle Routing Problem,Multi-Robot System,Rebalancing,Service-on-Demand},
 pages = {12-19},
 websites = {https://doi.org/10.3929/ethz-a-010025751},
 city = {Zürich},
 institution = {ETH Zürich},
 id = {87b41424-11c2-3ca0-ae40-47835973beaa},
 created = {2020-01-15T12:34:14.131Z},
 file_attached = {false},
 profile_id = {b8bb86b0-2c01-3ebb-b066-8c77b393d3cc},
 group_id = {8fe4ad94-b417-3a1e-85a0-b9d7ccc60bbd},
 last_modified = {2020-01-15T12:34:16.951Z},
 read = {true},
 starred = {false},
 authored = {false},
 confirmed = {true},
 hidden = {false},
 citation_key = {RuchClaudio;GachterJoel;HakenbergJan;Frazzoli2019c},
 folder_uuids = {c6702b10-cece-41f9-81bf-82b96f88115a},
 private_publication = {false},
 abstract = {Robotic multi-agent systems can efficiently handle spatially distributed tasks in dynamic environments. Problem instances of particular interest and generality are the dynamic vehicle routing problem and the dynamic traveling repairman problem. Operational policies for robotic fleets solving these two problems take decisions in an online setting with continuously arriving dynamic demands to optimize system time and efficiency. They can be classified along several lines. First, some require a model of the demand, e.g., based on historical information, while others work model-free. Second, they are designed for different operating conditions from light to heavy system load. Third, they work in a time-invariant or time-varying setting. We present a novel class of model-free operational policies for time-varying demands, with performance independent of the load factor and applicable to any number of dimensions, a combination of properties not achieved by any other operational policy in the literature. The underlying principle of the introduced policies is to send available robots to recent realizations of the stochastic process that generates service requests. In simple terms, the strategies rely on sending more than one robot for every service request arriving to the system. This leads to an advantage in scenarios where demand is non-uniformly distributed and correlated in space an time. We provide theoretical stability and performance guarantees for both the time-invariant and the time-varying cases as well as for correlated demand. We verify our theoretical results numerically. Finally, we apply our operational policy to the problem of mobility-on-demand fleet operation and demonstrate that it outperforms model-based and complex algorithms},
 bibtype = {unpublished},
 author = {Ruch, Claudio; Gächter, Joel; Hakenberg, Jan; Frazzoli, Emilio}
}

Downloads: 0

{"_id":"9RppMGxQwqQF7cTdY","bibbaseid":"ruch-the1methodmodelfreeadaptiverepositioningpoliciesforroboticmultiagentsystems-2019","authorIDs":[],"author_short":["Ruch, Claudio; Gächter, Joel; Hakenberg, Jan; Frazzoli, E."],"bibdata":{"title":"The +1 Method Model-Free Adaptive Repositioning Policies for Robotic Multi-Agent Systems","type":"unpublished","year":"2019","source":"ETH Zürich Research Colllection","identifiers":"[object Object]","keywords":"Anticipative Repositioning,Autonomous Mobility-on-Demand,Dispatching,Dynamic Traveling Repairman Problem,Dynamic Vehicle Routing Problem,Multi-Robot System,Rebalancing,Service-on-Demand","pages":"12-19","websites":"https://doi.org/10.3929/ethz-a-010025751","city":"Zürich","institution":"ETH Zürich","id":"87b41424-11c2-3ca0-ae40-47835973beaa","created":"2020-01-15T12:34:14.131Z","file_attached":false,"profile_id":"b8bb86b0-2c01-3ebb-b066-8c77b393d3cc","group_id":"8fe4ad94-b417-3a1e-85a0-b9d7ccc60bbd","last_modified":"2020-01-15T12:34:16.951Z","read":"true","starred":false,"authored":false,"confirmed":"true","hidden":false,"citation_key":"RuchClaudio;GachterJoel;HakenbergJan;Frazzoli2019c","folder_uuids":"c6702b10-cece-41f9-81bf-82b96f88115a","private_publication":false,"abstract":"Robotic multi-agent systems can efficiently handle spatially distributed tasks in dynamic environments. Problem instances of particular interest and generality are the dynamic vehicle routing problem and the dynamic traveling repairman problem. Operational policies for robotic fleets solving these two problems take decisions in an online setting with continuously arriving dynamic demands to optimize system time and efficiency. They can be classified along several lines. First, some require a model of the demand, e.g., based on historical information, while others work model-free. Second, they are designed for different operating conditions from light to heavy system load. Third, they work in a time-invariant or time-varying setting. We present a novel class of model-free operational policies for time-varying demands, with performance independent of the load factor and applicable to any number of dimensions, a combination of properties not achieved by any other operational policy in the literature. The underlying principle of the introduced policies is to send available robots to recent realizations of the stochastic process that generates service requests. In simple terms, the strategies rely on sending more than one robot for every service request arriving to the system. This leads to an advantage in scenarios where demand is non-uniformly distributed and correlated in space an time. We provide theoretical stability and performance guarantees for both the time-invariant and the time-varying cases as well as for correlated demand. We verify our theoretical results numerically. Finally, we apply our operational policy to the problem of mobility-on-demand fleet operation and demonstrate that it outperforms model-based and complex algorithms","bibtype":"unpublished","author":"Ruch, Claudio; Gächter, Joel; Hakenberg, Jan; Frazzoli, Emilio","bibtex":"@unpublished{\n title = {The +1 Method Model-Free Adaptive Repositioning Policies for Robotic Multi-Agent Systems},\n type = {unpublished},\n year = {2019},\n source = {ETH Zürich Research Colllection},\n identifiers = {[object Object]},\n keywords = {Anticipative Repositioning,Autonomous Mobility-on-Demand,Dispatching,Dynamic Traveling Repairman Problem,Dynamic Vehicle Routing Problem,Multi-Robot System,Rebalancing,Service-on-Demand},\n pages = {12-19},\n websites = {https://doi.org/10.3929/ethz-a-010025751},\n city = {Zürich},\n institution = {ETH Zürich},\n id = {87b41424-11c2-3ca0-ae40-47835973beaa},\n created = {2020-01-15T12:34:14.131Z},\n file_attached = {false},\n profile_id = {b8bb86b0-2c01-3ebb-b066-8c77b393d3cc},\n group_id = {8fe4ad94-b417-3a1e-85a0-b9d7ccc60bbd},\n last_modified = {2020-01-15T12:34:16.951Z},\n read = {true},\n starred = {false},\n authored = {false},\n confirmed = {true},\n hidden = {false},\n citation_key = {RuchClaudio;GachterJoel;HakenbergJan;Frazzoli2019c},\n folder_uuids = {c6702b10-cece-41f9-81bf-82b96f88115a},\n private_publication = {false},\n abstract = {Robotic multi-agent systems can efficiently handle spatially distributed tasks in dynamic environments. Problem instances of particular interest and generality are the dynamic vehicle routing problem and the dynamic traveling repairman problem. Operational policies for robotic fleets solving these two problems take decisions in an online setting with continuously arriving dynamic demands to optimize system time and efficiency. They can be classified along several lines. First, some require a model of the demand, e.g., based on historical information, while others work model-free. Second, they are designed for different operating conditions from light to heavy system load. Third, they work in a time-invariant or time-varying setting. We present a novel class of model-free operational policies for time-varying demands, with performance independent of the load factor and applicable to any number of dimensions, a combination of properties not achieved by any other operational policy in the literature. The underlying principle of the introduced policies is to send available robots to recent realizations of the stochastic process that generates service requests. In simple terms, the strategies rely on sending more than one robot for every service request arriving to the system. This leads to an advantage in scenarios where demand is non-uniformly distributed and correlated in space an time. We provide theoretical stability and performance guarantees for both the time-invariant and the time-varying cases as well as for correlated demand. We verify our theoretical results numerically. Finally, we apply our operational policy to the problem of mobility-on-demand fleet operation and demonstrate that it outperforms model-based and complex algorithms},\n bibtype = {unpublished},\n author = {Ruch, Claudio; Gächter, Joel; Hakenberg, Jan; Frazzoli, Emilio}\n}","author_short":["Ruch, Claudio; Gächter, Joel; Hakenberg, Jan; Frazzoli, E."],"urls":{"Website":"https://doi.org/10.3929/ethz-a-010025751"},"bibbaseid":"ruch-the1methodmodelfreeadaptiverepositioningpoliciesforroboticmultiagentsystems-2019","role":"author","keyword":["Anticipative Repositioning","Autonomous Mobility-on-Demand","Dispatching","Dynamic Traveling Repairman Problem","Dynamic Vehicle Routing Problem","Multi-Robot System","Rebalancing","Service-on-Demand"],"downloads":0},"bibtype":"unpublished","creationDate":"2020-01-15T12:20:52.453Z","downloads":0,"keywords":["anticipative repositioning","autonomous mobility-on-demand","dispatching","dynamic traveling repairman problem","dynamic vehicle routing problem","multi-robot system","rebalancing","service-on-demand"],"search_terms":["method","model","free","adaptive","repositioning","policies","robotic","multi","agent","systems","ruch"],"title":"The +1 Method Model-Free Adaptive Repositioning Policies for Robotic Multi-Agent Systems","year":2019}