• Omur.WAFR2014

Kod*lab Menu

Internal Links (Login Required)

<< Kod*lab Publications

Navigation of Distinct Euclidean Particles via Hierarchical Clustering

“Algorithmic Foundations of Robotics XI, 2015″

2014 International Workshop on the Algorithmic Foundations of Robotics, 2014

OmurArslan*, Dan P. Guralnik *, D. E. Koditschek*
*: Electrical and Systems Engineering, University of Pennsylvania
Full PDF | Penn Scholarly Commons | Springer

Hierarchical Navigation of Particles
Hierarchical Navigation of Particles
       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 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.
BibTeX entry
  Title                    = {Navigation of Distinct Euclidean Particles via Hierarchical Clustering},
  Author                   = {Arslan, Omur and Guralnik, Dan P. and Koditschek, Daniel E.},
  Booktitle                = {Algorithmic Foundations of Robotics XI},
  Publisher                = {Springer International Publishing},
  Year                     = {2015},
  Editor                   = {Akin, H. Levent and Amato, Nancy M. and Isler, Volkan and van der Stappen, A. Frank},
  Pages                    = {19-36},
  Series                   = {Springer Tracts in Advanced Robotics},
  Volume                   = {107},
  Doi                      = {10.1007/978-3-319-16595-0_2},
  Url                      = {http://dx.doi.org/10.1007/978-3-319-16595-0_2}

Copyright Kodlab, 2017