Abstract
We present a centralized online (completely reactive) hybrid navigation algorithm for bringing a swarm of \(n\) perfectly sensed and actuated point particles in Euclidean \(d\) space (for arbitrary \(n\) and \(d\)) to an arbitrary goal configuration with the guarantee of no collisions along the way. Our construction entails a discrete abstraction of configurations using cluster hierarchies, and relies upon two prior recent constructions: (i) a family of hierarchy-preserving control policies and (ii) an abstract discrete dynamical system for navigating through the space of cluster hierarchies. Here, we relate the (combinatorial) topology of hierarchical clusters to the (continuous) topology of configurations by constructing “portals”—open sets of configurations supporting two adjacent hierarchies. The resulting online sequential composition of hierarchy-invariant swarming followed by discrete selection of a hierarchy “closer” to that of the destination along with its continuous instantiation via an appropriate portal configuration yields a computationally effective construction for the desired navigation policy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We will mention in the conclusion a few such extensions presently in progress.
- 2.
- 3.
Here, \(\mathring{A}\) denotes the interior of set \(A\).
- 4.
- 5.
Note that for all \(\tau \in \mathcal {BT}_{J}\), \(\mathfrak {S}_o \left( \tau \right) \subseteq \mathring{\mathfrak {S}}\left( \tau \right) \).
- 6.
Here, \({\mathrm {\mathbf {A}}}^\mathrm {T}\) denotes the transpose of \(\mathrm {\mathbf {A}}\).
- 7.
Here, we use \(\eta _{i, I, \tau } : \left( \mathbb {R}^d\right) ^{J} \rightarrow \mathbb {R}\) (8).
- 8.
In a metric space \(\left( X, d\right) \), the open ball \(B\left( \mathrm {x},r\right) \) centered at \(\mathrm {x}\) with radius \(r \in \mathbb {R}_{\ge 0}\) is the set of points in \(X\) whose distance to \(\mathrm {x}\) is less than \(r\), i.e. \(B\left( \mathrm {x},r\right) = \left\{ \mathrm {y} \in X \; | \; d\left( \mathrm {x},\mathrm {y}\right) < r \right\} \).
- 9.
Here, we set \(\frac{\mathrm {x}}{\left\| \mathrm {x}\right\| _2} = 0\) for \(\mathrm {x} = 0\).
- 10.
Here, \(\mathrm {\mathbf {I}}_{d}\) is the \(d \times d\) identity matrix, and \(\mathrm {\mathbf {1}}_k\) is the \(\mathbb {R}^k\) column vector of all ones. Also, \(\otimes \) and \(\cdot \) denote the Kronecker product and the standard array product, respectively.
References
Adler, A., de Berg, M., Halperin, D., Solovey, K.: Efficient multi-robot motion planning for unlabeled discs in simple polygons. In: 30th European Workshop on Computational Geometry (EuroCG 2014) (2013)
Arnold, V.I.: Ordinary Differential Equations. MIT Press (1973)
Arslan, O., Guralnik, D.P., Koditschek, D.E.: Navigation of distinct Euclidean particles via hierarchical clustering (extended version). Technical report, University of Pennsylvania (2013). http://kodlab.seas.upenn.edu/Omur/TechReport2013
Arslan, O., Guralnik, D., Koditschek, D.E.: Discriminative measures for comparison of phylogenetic trees. Technical report, University of Pennsylvania (2013). http://arxiv.org/abs/1310.5202
Arslan, O., Guralnik, D.P., Koditschek, D.E.: Hierarchically clustered navigation of distinct euclidean particles. In: 50th Annual Allerton Conference on Communication, Control, and Computing (2012). http://kodlab.seas.upenn.edu/Main/Allerton2012
Ayanian, N., Kumar, V., Koditschek, D.: Synthesis of controllers to create, maintain, and reconfigure robot formations with communication constraints. In: Robotics Research. Springer Tracts in Advanced Robotics, vol. 70, pp. 625–642 (2011)
Baryshnikov, Y., Bubenik, P., Kahle, M.: Min-type Morse theory for configuration spaces of hard spheres. International Mathematics Research Notices (2013)
Billera, L.J., Holmes, S.P., Vogtmann, K.: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27(4), 733–767 (2001)
Burridge, R.R., Rizzi, A.A., Koditschek, D.E.: Sequential composition of dynamically dexterous robot behaviors. Int. J. Robot. Res. 18(6), 534–555 (1999)
Choi, Y.C., Ahn, H.S.: Formation control of quad-rotors in three dimension based on Euclidean distance dynamics matrix. In: 2011 11th International Conference on Control, Automation and Systems (ICCAS), pp. 1168–1173 (2011)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press (2009)
Coxeter, H.S.M., Greitzer, S.L.: Geometry Revisited, vol. 19. Mathematical Association of America (1996)
DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Zhang, L.: On distances between phylogenetic trees. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 427–436. Society for Industrial and Applied Mathematics (1997)
Dimarogonas, D.V., Loizou, S.G., Kyriakopoulos, K.J., Zavlanos, M.M.: A feedback stabilization and collision avoidance scheme for multiple independent non-point agents. Automatica 42(2), 229–243 (2006)
Fadell, E.R., Husseini, S.Y.: Geometry and Topology of Configuration Spaces. Springer (2001)
Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc. (2004)
Hatcher, A.: Algebraic Topology. Cambridge University Press (2002)
Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice-Hall, Inc. (1988)
Karagoz, C.S., Bozma, H.I., Koditschek, D.E.: Coordinated motion of disk-shaped independent robots in 2d workspaces. University Michigan, Ann Arbor, Technical report. CSE-TR-486-04, February (2004)
Koditschek, D.E.: Adaptive techniques for mechanical systems. In: Proceedings of the 5th, Yale Workshop on Adaptive Systems, May 1987, pp. 259–265 (1987)
Koditschek, D.E.: Some applications of natural motion control. J. Dyn. Syst., Meas., Control 113, 552–557 (1991)
Liu, Y.H., Kuroda, S., Naniwa, T., Noborio, H., Arimoto, S.: A practical algorithm for planning collision-free coordinated motion of multiple mobile robots. In: Proceedings of the 1989 IEEE International Conference on Robotics and Automation, pp. 1427–1432 (1989)
Liu, Y.H., Arimoto, S., Noborio, H.: New solid model HSM and its application to interference detection between moving objects. J. Robot. Syst. 8(1), 39–54 (1991)
Lozano-Perez, T., Mason, M.T., Taylor, R.H.: Automatic synthesis of fine-motion strategies for robots. Int. J. Robot. Res. 3(1), 3–24 (1984)
Mirkin, B.: Mathematical Classification and Clustering. Kluwer Academic Publishers (1996)
Moore, G., Goodman, M., Barnabas, J.: An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posed by molecular data sets. J. Theor. Biol. 38(3), 423–457 (1973)
Oh, K.K., Ahn, H.S.: Distance-based formation control using euclidean distance dynamics matrix: three-agent case. In: American Control Conference (ACC), July 2011, pp. 4810–4815 (2011)
Rimon, E., Koditschek, D.: Exact robot navigation using artificial potential functions. IEEE Trans. Robot. Autom. 8(5), 501–518 (1992)
Robinson, D.: Comparison of labeled trees with valency three. J. Comb. Theory, Ser. B 11(2), 105–119 (1971)
Savaresi, S.M., Boley, D.L.: On the performance of bisecting k-means and PDDP. In: Proceedings of the First SIAM International Conference on Data Mining (ICDM 2001), pp. 1–14 (2001)
Solovey, K., Halperin, D.: k-color multi-robot motion planning. Int. J. Robot. Res. 33(1), 82–97 (2014)
Spirakis, P., Yap, C.K.: Strong np-hardness of moving many discs. Inf. Process. Lett. 19(1), 55–59 (1984)
Tanner, H., Boddu, A.: Multiagent navigation functions revisited. IEEE Trans. Robot. 28(6), 1346–1359 (2012)
Turpin, M., Michael, N., Kumar, V.: Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In: 2013 IEEE International Conference on Robotics and Automation (ICRA), pp. 842–848, IEEE. (2013)
Whitcomb, L.L., Koditschek, D.E., Cabrera, J.B.D.: Toward the automatic control of robot assembly tasks via potential functions: the case of 2-d sphere assemblies. In: Proceedings., 1992 IEEE International Conference on Robotics and Automation, pp. 2186–2191 (1992)
Whitcomb, L.L., Koditschek, D.E.: Automatic assembly planning and control via potential functions. In: Proceedings IROS91. IEEE/RSJ International Workshop on Intelligent Robots and Systems 91, Intelligence for Mechanical Systems, pp. 17–23 (1991)
Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann (2005)
Acknowledgments
This work was supported in part by AFOSR under the CHASE MURI FA9550-10-1-0567 and in part by ONR under the HUNT MURI N00014070829.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Arslan, O., Guralnik, D.P., Koditschek, D.E. (2015). Navigation of Distinct Euclidean Particles via Hierarchical Clustering. In: Akin, H., Amato, N., Isler, V., van der Stappen, A. (eds) Algorithmic Foundations of Robotics XI. Springer Tracts in Advanced Robotics, vol 107. Springer, Cham. https://doi.org/10.1007/978-3-319-16595-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-16595-0_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16594-3
Online ISBN: 978-3-319-16595-0
eBook Packages: EngineeringEngineering (R0)