×

Efficient motion planning strategies for large-scale sensor networks. (English) Zbl 1194.93016

Akella, Srinivas (ed.) et al., Algorithmic foundation of robotics VII. Selected contributions of the seventh international workshop on the algorithmic foundations of robotics (WAFR 2006), New York, NJ, USA, July 16–18, 2006. Berlin: Springer (ISBN 978-3-540-68404-6/hbk; 978-3-540-68405-3/ebook). Springer Tracts in Advanced Robotics 47, 441-456 (2008).
Summary: In this paper, we develop a suite of motion planning strategies suitable for large-scale sensor networks. These solve the problem of reconfiguring the network to a new shape while minimizing either the total distance traveled by the nodes or the maximum distance traveled by any node. Three network paradigms are investigated: centralized, computationally distributed, and decentralized. For the centralized case, optimal solutions are obtained in \(O(m)\) time in practice using a logarithmic-barrier method. Key to this complexity is transforming the Karush-Kuhn-Tucker (KKT) matrix associated with the Newton step sub-problem into a mono-banded system solvable in \(O(m)\) time. These results are then extended to a distributed approach that allows the computation to be evenly partitioned across the \(m\) nodes in exchange for \(O(m)\) messages in the overlay network. Finally, we offer a decentralized, hierarchical approach whereby follower nodes are able to solve for their objective positions in \(O(1)\) time from observing the headings of a small number (2–4) of leader nodes. This is akin to biological systems (e.g. schools of fish, flocks of birds, etc.) capable of complex formation changes using only local sensor feedback. We expect these results will prove useful in extending the mission lives of large-scale mobile sensor networks.
For the entire collection see [Zbl 1155.93004].

MSC:

93A15 Large-scale systems
93C85 Automated systems (robots, etc.) in control theory
49N90 Applications of optimal control and differential games

Software:

Mosek
PDFBibTeX XMLCite
Full Text: DOI