Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks
A widely applied strategy for workload sharing is to equalize the workload assigned to each resource. In mobile multiagent systems, this principle directly leads to equitable partitioning policies whereby: 1) the environment is equitably divided into subregions of equal measure; 2) one agent is assi...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81455 https://orcid.org/0000-0002-0505-1400 |
| _version_ | 1811088431720169472 |
|---|---|
| author | Pavone, Marco Arsie, Alessandro Frazzoli, Emilio Bullo, Francesco |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Pavone, Marco Arsie, Alessandro Frazzoli, Emilio Bullo, Francesco |
| author_sort | Pavone, Marco |
| collection | MIT |
| description | A widely applied strategy for workload sharing is to equalize the workload assigned to each resource. In mobile multiagent systems, this principle directly leads to equitable partitioning policies whereby: 1) the environment is equitably divided into subregions of equal measure; 2) one agent is assigned to each subregion; and 3) each agent is responsible for service requests originating within its own subregion. The current lack of distributed algorithms for the computation of equitable partitions limits the applicability of equitable partitioning policies to limited-size multiagent systems operating in known, static environments. In this paper, first we design provably correct and spatially distributed algorithms that allow a team of agents to compute a convex and equitable partition of a convex environment. Second, we discuss how these algorithms can be extended so that a team of agents can compute, in a spatially distributed fashion, convex and equitable partitions with additional features, e.g., equitable and median Voronoi diagrams. Finally, we discuss two application domains for our algorithms, namely dynamic vehicle routing for mobile robotic networks and wireless ad hoc networks. Through these examples, we show how one can couple the algorithms presented in this paper with equitable partitioning policies to make these amenable to distributed implementation. More in general, we illustrate a systematic approach to devise spatially distributed control policies for a large variety of multiagent coordination problems. Our approach is related to the classic Lloyd algorithm and exploits the unique features of power diagrams. |
| first_indexed | 2024-09-23T14:02:05Z |
| format | Article |
| id | mit-1721.1/81455 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:02:05Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/814552022-09-28T17:50:44Z Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks Pavone, Marco Arsie, Alessandro Frazzoli, Emilio Bullo, Francesco Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Frazzoli, Emilio A widely applied strategy for workload sharing is to equalize the workload assigned to each resource. In mobile multiagent systems, this principle directly leads to equitable partitioning policies whereby: 1) the environment is equitably divided into subregions of equal measure; 2) one agent is assigned to each subregion; and 3) each agent is responsible for service requests originating within its own subregion. The current lack of distributed algorithms for the computation of equitable partitions limits the applicability of equitable partitioning policies to limited-size multiagent systems operating in known, static environments. In this paper, first we design provably correct and spatially distributed algorithms that allow a team of agents to compute a convex and equitable partition of a convex environment. Second, we discuss how these algorithms can be extended so that a team of agents can compute, in a spatially distributed fashion, convex and equitable partitions with additional features, e.g., equitable and median Voronoi diagrams. Finally, we discuss two application domains for our algorithms, namely dynamic vehicle routing for mobile robotic networks and wireless ad hoc networks. Through these examples, we show how one can couple the algorithms presented in this paper with equitable partitioning policies to make these amenable to distributed implementation. More in general, we illustrate a systematic approach to devise spatially distributed control policies for a large variety of multiagent coordination problems. Our approach is related to the classic Lloyd algorithm and exploits the unique features of power diagrams. National Science Foundation (U.S.) (Grant 0705451) National Science Foundation (U.S.) (Grant 0705453) United States. Office of Naval Research (Grant N00014-07-1-0721) 2013-10-21T16:06:25Z 2013-10-21T16:06:25Z 2011-08 2010-12 Article http://purl.org/eprint/type/JournalArticle 0018-9286 1558-2523 http://hdl.handle.net/1721.1/81455 Pavone, Marco, Alessandro Arsie, Emilio Frazzoli, and Francesco Bullo. “Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks.” IEEE Transactions on Automatic Control 56, no. 8 (August 2011): 1834-1848. https://orcid.org/0000-0002-0505-1400 en_US http://dx.doi.org/10.1109/tac.2011.2112410 IEEE Transactions on Automatic Control Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT Web domain |
| spellingShingle | Pavone, Marco Arsie, Alessandro Frazzoli, Emilio Bullo, Francesco Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks |
| title | Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks |
| title_full | Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks |
| title_fullStr | Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks |
| title_full_unstemmed | Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks |
| title_short | Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks |
| title_sort | distributed algorithms for environment partitioning in mobile robotic networks |
| url | http://hdl.handle.net/1721.1/81455 https://orcid.org/0000-0002-0505-1400 |
| work_keys_str_mv | AT pavonemarco distributedalgorithmsforenvironmentpartitioninginmobileroboticnetworks AT arsiealessandro distributedalgorithmsforenvironmentpartitioninginmobileroboticnetworks AT frazzoliemilio distributedalgorithmsforenvironmentpartitioninginmobileroboticnetworks AT bullofrancesco distributedalgorithmsforenvironmentpartitioninginmobileroboticnetworks |