K-robots clustering of moving sensors using coresets
We present an approach to position k servers (e.g. mobile robots) to provide a service to n independently moving clients; for example, in mobile ad-hoc networking applications where inter-agent distances need to be minimized, connectivity constraints exist between servers, and no a priori knowledge...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90592 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0002-3964-2049 |
| _version_ | 1826206639945940992 |
|---|---|
| author | Feldman, Dan Gil, Stephanie Knepper, Ross A. Julian, Brian John Rus, Daniela L. |
| author2 | Lincoln Laboratory |
| author_facet | Lincoln Laboratory Feldman, Dan Gil, Stephanie Knepper, Ross A. Julian, Brian John Rus, Daniela L. |
| author_sort | Feldman, Dan |
| collection | MIT |
| description | We present an approach to position k servers (e.g. mobile robots) to provide a service to n independently moving clients; for example, in mobile ad-hoc networking applications where inter-agent distances need to be minimized, connectivity constraints exist between servers, and no a priori knowledge of the clients' motion can be assumed. Our primary contribution is an algorithm to compute and maintain a small representative set, called a kinematic coreset, of the n moving clients.We prove that, in any given moment, the maximum distance between the clients and any set of k servers is approximated by the coreset up to a factor of (1 ± ε), where ε > 0 is an arbitrarily small constant. We prove that both the size of our coreset and its update time is polynomial in k log(n)/ε. Although our optimization problem is NP-hard (i.e., takes time exponential in the number of servers to solve), solving it on the small coreset instead of the original clients results in a tractable controller. The approach is validated in a small scale hardware experiment using robot servers and human clients, and in a large scale numerical simulation using thousands of clients. |
| first_indexed | 2024-09-23T13:35:48Z |
| format | Article |
| id | mit-1721.1/90592 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:35:48Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/905922022-10-01T15:56:08Z K-robots clustering of moving sensors using coresets Feldman, Dan Gil, Stephanie Knepper, Ross A. Julian, Brian John Rus, Daniela L. Lincoln Laboratory Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. School of Engineering Feldman, Dan Gil, Stephanie Knepper, Ross A. Julian, Brian John Rus, Daniela L. We present an approach to position k servers (e.g. mobile robots) to provide a service to n independently moving clients; for example, in mobile ad-hoc networking applications where inter-agent distances need to be minimized, connectivity constraints exist between servers, and no a priori knowledge of the clients' motion can be assumed. Our primary contribution is an algorithm to compute and maintain a small representative set, called a kinematic coreset, of the n moving clients.We prove that, in any given moment, the maximum distance between the clients and any set of k servers is approximated by the coreset up to a factor of (1 ± ε), where ε > 0 is an arbitrarily small constant. We prove that both the size of our coreset and its update time is polynomial in k log(n)/ε. Although our optimization problem is NP-hard (i.e., takes time exponential in the number of servers to solve), solving it on the small coreset instead of the original clients results in a tractable controller. The approach is validated in a small scale hardware experiment using robot servers and human clients, and in a large scale numerical simulation using thousands of clients. Micro Autonomous Consortium Systems and Technology (United States. Army Research Laboratory (Grant W911NF-08-2-0004)) United States. Air Force (Contract FA8721-05-C-0002) 2014-10-07T18:19:28Z 2014-10-07T18:19:28Z 2013-05 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-5643-5 978-1-4673-5641-1 1050-4729 http://hdl.handle.net/1721.1/90592 Feldman, Dan, Stephanie Gil, Ross A. Knepper, Brian Julian, and Daniela Rus. “K-Robots Clustering of Moving Sensors Using Coresets.” 2013 IEEE International Conference on Robotics and Automation (May 2013). https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0002-3964-2049 en_US http://dx.doi.org/10.1109/ICRA.2013.6630677 Proceedings of the 2013 IEEE International Conference on Robotics and Automation Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Feldman, Dan Gil, Stephanie Knepper, Ross A. Julian, Brian John Rus, Daniela L. K-robots clustering of moving sensors using coresets |
| title | K-robots clustering of moving sensors using coresets |
| title_full | K-robots clustering of moving sensors using coresets |
| title_fullStr | K-robots clustering of moving sensors using coresets |
| title_full_unstemmed | K-robots clustering of moving sensors using coresets |
| title_short | K-robots clustering of moving sensors using coresets |
| title_sort | k robots clustering of moving sensors using coresets |
| url | http://hdl.handle.net/1721.1/90592 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0002-3964-2049 |
| work_keys_str_mv | AT feldmandan krobotsclusteringofmovingsensorsusingcoresets AT gilstephanie krobotsclusteringofmovingsensorsusingcoresets AT knepperrossa krobotsclusteringofmovingsensorsusingcoresets AT julianbrianjohn krobotsclusteringofmovingsensorsusingcoresets AT rusdanielal krobotsclusteringofmovingsensorsusingcoresets |