Lattice Formation in Mobile Autonomous Sensor Arrays

Eric Martinson†, David Payton

HRL Laboratories LLC

payton@hrl.com

†Currently at Georgia Tech

GOAL:

Use arrays of inexpensive tiny sensors to supplement today’s larger imaging sensors

Acoustic / seismic sensors arrays can provide target tracking where LOS sensors are infeasible

PROBLEM:

Array deployment can require manual placement to achieve desired accuracy

SOLUTION:

Autonomous array deployment can allow faster deployment with less manpower

Distributed coordinated control is needed

Distributed Robotic Sensor Nets

Acoustic / Seismic
Arrays

Multiple Arrays Provide Range and Azimuth Estimates to Vehicles on Road

Sensor Placement Issues

Currently a manual process

Concepts exist for automatic deployment into patterns with desired statistics

Relative locations
and long-range
order impact array
effectiveness

Robotic deployment
offers an opportunity
to achieve ordered
arrays with minimal
human intervention

US Army Corps of Engineers ERDC-CRREL deployment concept

Autonomous Pattern Forming Robots

Principal goal -- use an ensemble of autonomous mobile robots to sense seismic and acoustic signals.

Desired characteristics:

Minimal external control or intervention required.

Solution needs to be flexible and valid for forming a variety of spatial structures.

Scalable approach; valid from 10 to 106 elements.

Capable of working with groups of several vehicle types.

Form long-range ordered patterns based on only local information.

No GPS requirement.

Cooperating Robotic Sensor Nodes

emergent group behavior is generated from simple local interactions

local messaging & sensing of neighbors facilitates local interactions

DARPA

Pheromone Robotics

Sensor Array Optimization

Deployment of sensor carrying mobile robots.

2.	Autonomous sensor array optimization.

3. Frequency and spatially optimized sensing.



(further optimization and/or patterning based on sensor data input.)

sensing

ordering

initial distribution

source

Related Work In Pattern Formation

“Behavior-Based Coordination of Large-Scale Robot Formations”
Tucker Balch, Maria Hybinette

Problems:

Attachment points are generated according to detected robot alignment.

With no defined goal to align the robots, the noise vector causes the robots to change orientation and destabilize the formation.

Behavior Schemas

Avoid Obstacles

Avoid Robots

Move to Goal

Move to Unit Center

Noise

Maintain Formation

Build list of all possible attachment points around visible robots.

Move to nearest attachment point.

X

X

X

X

X

X

X

X

New Robot is drawn

towards closest

attachment point

Related Work (cont.)

“Using Artificial Physics to Control Agents”
W. Spears and D. Gordon

Problems:

Many local minima

Two robots tend to compete for the same position

Behavior Schemas

G/R2 forces

Attraction if R > Rt and
repulsion otherwise

Differentiation into
alternating “spin” states

Different values for Rt
for like spins versus
unlike spins creates
a rectangular lattice

Basic Spring Model

Behavior Schemas

Avoid Obstacles

Avoid Robots

Noise

Spring Force

Which robots should we attach springs to?

Fitness = f(angles,distances)

Have to allow for missing springs (i.e. Corners, edges in formation).

Avoid Obstacles

∑

Avoid Robots

Noise

Spring Force

Common Problems

Zipper

Two arrays at different angles need to close together and re-align.

Outlier

A single robot needs to join the array, but there is no place to join.

Man in the middle

An extra robot in the middle of the array causes deformations.

Separate Arrays

The robots form two separate and distinct arrays, that are not aligned with each other.

Lost Robots

Outlier Robot

Man in the Middle

Solution 1: Local Annealing

Basic Concept:

Change the noise gain when the fitness score is poor.

Method 1: “Heat”

Noisegain = exp (fitness score)

Method 2: “Hotspot”

Noisegain = integral of fitness score over time.

Hot robots increase noise gain to find place in array

Key Insight

Spacing Robots in 1-D Has No Local Minima

“Nullspace Composition of Control Laws for Grasping”
R. Platt, A. Fagg, and R. Grupen

Appropriate Nullspace Composition of 1-D Controllers Should
Yield A Suitable Controller for 2-D

Solution 2: Line Force

Solve the 1D spacing problem independently on orthogonal axes

Special assumption: A reference axis may be obtained from on-board compass
Tested for robustness to compass error

Reference Axis

Form Lines Parallel
to a Reference Axis

Adjust Spacing
Within Lines

Adjust Offsets
Between Lines

Spacing along a single axis has no local minima!

Applying 1D spacing along orthogonal axes significantly reduces local minima.

Hypothesis Generation Method

For every neighbor to a target robot, construct a hypothesis of where the array lines should be.

Hypothesis passing

through center of detected neighbor.

Best Hypothesis

Choose the “best” hypothesis as the one which passes trough the most robots or which clusters closely with other hypotheses

Drive the target robot toward the closest line of the “best” hypothesis

Simulation Examples

Spears-Gordon

Method

Local Annealing

Method

Hypothesis
Generation

Method

Local minima cause the first two methods to converge slowly and often with errors.

Comparative Performance

Best Prior Art
(Spears & Gordon)

Our Best Method

(Hypothesis Generation)

Comparative Performance

Performance With Noisy Sensors

Errors DECREASE with some amount of compass noise!

Performance With Noisy Sensors

The approach is highly robust to ordinary noise in
measuring distance and angle to local neighbors

Summary

2-D Pattern Formation by Mobile Robots is Subject to Many Local Minima

Divide the 2-D Pattern Formation Problem into Non-Interfering Orthogonal 1-D controllers

Local Annealing Provides a General Additional Tool to Reduce Local Minima in Any Method Used

Sensor Noise Can Be Beneficial if Attractors for Local Minima are Small

Caveat: The Line-Force Method Assumes an Additional Sensor	Reading That Is Common to All Robots

2

2

2

2

2

Our previous SR work has explored the idea of taking a network of distributed sensors, and of having individual sensors differentiate themselves so that together, they form a large-scale spatial pattern. Depending on how they have differentiated themselves, nodes can then interact with each other to form a distributed detector. Through interactions with ISL’s computational physics department, we hope to extend these ideas using insights from pattern formation in dynamical systems.

Our goal is to establish patterning primitives deployable on the HRL pheromone robot system and scalable to the limits of large robot number and high robot density. Patterns based on and derived from the full group of two-dimensional solids can be generated autonomously by a group of distributed robots. Individual robots need only possess information about their local environment, e.g. coordination number and basis vectors of desired pattern. Directives may come from within the group, via onboard AI algorithms, or externally from an operator/controller. Operator input may be limited to the communication of directives to a single member of the group which can then initiate propagation of the directive to the whole group. Subsequent pattern formation may not require any interaction with the operator/controller. Patterning may also be self-adjusted by the group to satisfy sensing and space coverage requirements.

No Slide Title

David Payton

2004-07-18T16:56:08