Worst-Case Time Complexity of a Lattice Formation Problem

Abstract

We consider a formation control problem for a robotic network with limited communication and controlled motion abilities. We propose a novel control structure that organizes the robots in concentric layers and that associates to each layer a local leader. Through a load balancing algorithm on the asynchronous network of layers we allocate the desired number of robots on each layer. A final uniform spreading algorithm leads the robots to a lattice-like formation. This novel distributed communication and control algorithm runs in linear time in the worst case.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 29, 2006
Accession Number
AD1005961

Entities

People

  • Francesco Bullo
  • Ketan Savla

Organizations

  • University of California, Santa Barbara

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Control Systems
  • Deployment
  • Elections
  • Engineering
  • Intervals
  • Linear Systems
  • Mechanics
  • Motion Planning
  • Robots
  • Scaling Laws
  • Statistical Mechanics
  • Time Intervals
  • Wireless Communications

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Fluid Mechanics and Fluid Dynamics.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Autonomous Systems
  • AI & ML - Machine Learning Algorithms
  • Autonomy
  • Autonomy - Autonomous System Control