• Omur.TechReport2013

Kod*lab Menu

Internal Links (Login Required)

<< Kod*lab Publications

Navigation of Distinct Euclidean Particles via Hierarchical Clustering (Extended Version)

ESE Technical Report

October, 2013

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

Hierarchical Navigation of Particles
Hierarchical Navigation of Particles
       We present a centralized, online (completely reactive) algorithm for bringing a swarm of n perfectly sensed and actuated particles in Euclidean d space (for arbitrary n and d) to an arbitrary goal configuration with the guarantee of no collisions along the way. This result relies upon two prior constructions. First, in an earlier paper, we develop a hybrid dynamical system for maintaining the swarm in a specified hierarchical arrangement of clusters while servoing toward any desired configuration that supports the hierarchy, including the guarantee of no self-collisions along the way. Second, in separate work, we show how to build a discrete dynamical system for navigating through the space of abstract hierarchical clusters of n particles that is guaranteed to reach a desired hierarchy in O(n2) steps, each step costing O(n) computations. In this paper 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 location in the configuration space yields 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
author       = {Arslan, O. and Guralnik, D. P.  and Koditschek, D. E.},
title        = {Navigation of Distinct Euclidean Particles via Hierarchical Clustering (Extended version)},
institution  = {University Of Pennsylvania},
year         = {2013}

Copyright Kodlab, 2017