Transcript Mobile Sensor Network Deployment using Potential Fields

Mobile Sensor Network Deployment
using Potential Fields : A Distributed,
Scalable Solution to the Area Coverage
Problem
Andrew Howard, Maja J Mataric´ , and Gaurav S
Sukhatme
Robitics Research Laboratories, Dept. of Computer
Science, University of Southern California, Los
Angeles.
International Symposium on Dustributed Autonomous
1
Robotics Systems (DARS02)
Outline







Introduction
Related Work
Potential Fields
Equation of Motion and Control Law
Static Equilibrium
Experiments
Conclusion and further work
2
Introduction

A mobile sensor network is composed of
mobile sensor nodes.

Mobile sensor node has communication
sensing, computation, and locomotion
capabilities.

Locomotion facilitates a number of useful
network, including the self-deploy ability.
3
Introduction

Deployment environment may be hostile and
dynamic.


Ex: Damaged building
Target environment gives two constraints :

Model of environment are either incomplete,
inaccurate or unavailable.

Sensor nodes may be lost or destroyed.
4
Introduction

This paper describes a potential-field-based
approach to deployment.

The only assumption is each sensor node
can determine the range and bearing of
nearby nodes and obstacles.

The approach does not require model of
environment or centralized control.
5
Related Work

Coverage type of many-robot system [5] :




Blanket coverage:
 reach a static arrangement of nodes that maximize
the total detection area.
Barrier coverage:
 minimize the probability of undetected penetration
through the barrier.

Sweep coverage:

 more-or-less equivalent to a moving barrier.
* [5] D. W. Gate. Command control for many-robot system.
6
Related Work

Related problems

Potential field techniques for local navigation and obstacle
avoidance problem [10]
* [10] O. Khatib. Real-time obstacles avoidance for manipulators and mobile robots.

Multi-robot exploration and mapping problem [3, 4, 14, 15]
* [3] W. Burgard, M. Moors, D. Fox, R. Simmons, and S. Thrun. Collaborative multi-robot exploration.
* [4] G. Dedeoglu and G. S. Sukhatme. Landmark-based matching algorithms for cooperation mapping by
autonomous robots.
* [14] R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, and H. Younes. Coordination for
multi-robot exploration and mapping.
* [15] S. Thrun, W. Burgard, and D. Fox. A real-time algorithm for mobile robot mapping with applications to
multi-robot and 3d mapping.

Traditional art gallery problem [12]
* [12] J. O’Rourke. Art Gallery Theorems and Algorithms.
7
Potential Fields

Each node is subject to force F from potential field U.
F   U

Divide potential field into two component


U o due to obstacles
U n due to sensor nodes
U  Uo  Un
F  Fo  Fn
8
Potential Fields

Potential due to obstacles
1
U o  ko 
ri
i



: obstacles seen by the node
ko : constant strength of the field
ri : Euclidean distance between the node and obstacle i;
ri  xi  x , x denote the position of node, x i denote
the position of obstacle i.
9
Potential Fields

Total force due to obstacles
dUo dUo dri
1 ri
Fo  U o  


 k o  2 
dx
dri dx
ri
i ri
ri  xi  x , ri  xi  x

ri
 1
ri
The force is expressed entirely in terms of the
relative position of obstacles, it allows us compute
directly from sensed data.
10
Potential Fields
Fig.1. (a) Potential field generated by
A simple environment; the contours
show the lines of equal potential.
Fig. 1. (b) Force field generated by
The potential field; arrows indicate
the direction (but not magnitude)
of the force.
11
Potential Fields

Total force due to other nodes
1
U n  kn 
i ri
Fn  k n 
i

1 ri

2
ri
ri
: constant strength of the nodes field
12
Equation of Motion

Equation of motion





: the acceleration of the node
: the velocity of the node
: the mass of the node
: viscous coefficient
This viscous friction term “ “ is used to ensure that
the node will come to a standstill in the absence of
external forces.
13
Control Law

Use control law to map virtual physical system to
real system.

Real nodes have both kinematic and dynamic
constraints.


Assuming the nodes have holonomic drive mechanisms to
ignore kinematic constraint.
Dynamic constraint can’t be ignored.


Nodes have both maximum velocity and maximum
acceleration.
Control law should capture dynamic constraint.
14
Control Law

Change of commanded velocity is determined by
using piecewise-constant approximation.
with


is the largest allowable change in velocity.
The commanded velocity is determined:
with

is the maximum allowable velocity.
15
Control Law

Two regimes in which the correspondence
will fail.


For small velocity, the viscous friction term will
tend to produce oscillation to zero velocities.

Typical behavior of discrete control system.

Can be eliminated by a velocity ‘dead-band’.
Large acceleration and velocities will be clipped.

It increases time taken to reach equilibrium.

Impact must be determined empirically.
16
Static Equilibrium

The network will reach a static equilibrium

System energy is composed of potential and
kinetic energy.

Total energy is determined by initialization.

Viscous friction term of motion equation has the
effect of removing energy.
The system is dissipative
The network must asymptotically approach static equilibrium
17
Static Equilibrium

Above argument rests on the assumption that
the environment is static.

The network may not reach equilibrium in
continually changing environment.

The network will reach static equilibrium in
periodically or intermittently environment, but
the equilibrium may be different after change.
18
Experiments

Experiment environment

100 sensor nodes with scanning laser.

Laser range is 4m and 360 degree field-of-view.

Maximum velocity is 0.5 m/s

Simulated by using Player robot server[7] and the
Stage[17,6] multi-agent simulator.
19
Experiments
Fig. 2. (a) Initial network configuration.
20
Experiments
Fig. 2. (b) Final configuration after 300 seconds.
21
Experiments
Fig. 2. (c) Occupancy grid generated for the final configuration;
visible space is marked in black (occupied) or white (free);
unseen space is marked in gray.
22
Experiments
Fig. 3. Network coverage area and average node separation
as function of time for a 100-node deployment experiment.
The coverage and separation are plotted on different scales.
23
Experiments

The node spacing is even (about 1.6±0.4m).

No gaps or breaks in the coverage.

Rate of coverage decreases with time.

Final configuration (500m2) is 10-fold improvement
over the initial configuration (50 m2).

Average velocity of boundary nodes in the early
phase is higher.
24
Conclusion

Potential field approach can be used to
deploy mobile sensor network.

It is a distributed and scalable approach.

It has provable convergence characteristics.
25
Future Works

More experiments with different factors



Internal factors: environment, initial condition…
External factors: strength of fields, node mass,
viscosity coefficient…
Apply approach to coverage problems in
which line-of-sight connectivity is important.
26