payton research

Slide1: 

Lattice Formation in Mobile Autonomous Sensor Arrays Eric Martinson†, David Payton HRL Laboratories LLC payton@hrl.com †Currently at Georgia Tech

Distributed Robotic Sensor Nets: 

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: 

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: 

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: 

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: 

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: 

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.): 

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: 

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).

Common Problems: 

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: 

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: 

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: 

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 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: 

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. 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: 

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: 

Comparative Performance Best Prior Art (Spears & Gordon) Our Best Method (Hypothesis Generation)

Comparative Performance: 

Comparative Performance

Performance With Noisy Sensors: 

Performance With Noisy Sensors Errors DECREASE with some amount of compass noise!

Performance With Noisy Sensors: 

Performance With Noisy Sensors The approach is highly robust to ordinary noise in measuring distance and angle to local neighbors

Summary: 

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