Transcript DynamicSelfOrganizat.. - Duke Computer Science

Dynamic Self-Organization &
Computation by Natural and
Artificial Potential Fields
John H Reif
Duke University
Download:
www.cs.duke.edu/~reif/paper/DynamicSelfOrganization
Example of Natural Potential Fields
- Gravitation Force Fields (date to Newton in
1600s)
- Electrostatic Force Fields e.g., Coulomb
attraction (dates to 1700s)
- Magnetic Force Fields (dates to 1800s)
- Social Behavior (eg Flocking) by Groups of
Animals (dates to 1800s)
- Molecular Force Fields (dates to 1900s)
Closed Form Solution of 2 Particle Systems
- For 2 particle systems:
- Quadratic trajectories definable in closed form
- Proof dates at least to Newton’s Philosophiæ
Naturalis Principia Mathematica (1676)
Closed Form Solution of 3 Particle Systems
- Except in special cases, the motion of three
bodies is generally non-repeating
- Would like an analytical solution given by
algebraic expressions and integrals.
- Posed as open problem in Newton’s
Philosophiæ Naturalis Principia Mathematica
(1676)
- Henri Poincaré (1887) proved there is no
general analytical solution of the general threebody problem.
n-Body Simulation
- Given: the initial positions and velocities of n
particles that have pair-wise inverse power
force interactions
- The n-body simulation problem is to simulate
the movement of these particles so as to
determine these particles at a future time.
- The reachability problem is to determine if a
specific particle will reach a certain specified
region at some specified target time.
Computational Complexity of n-body Simulation
Steve R. Tate and John H. Reif, The Complexity of
N-body Simulation, Proceedings of the 20th Annual Colloquium on
Automata, Languages and Programming (ICALP'93), Lund, Sweden, July, 1993,
pp. 162-176.
- Proof that the n-body Simulation reachability
problem for a set of interacting particles in
three dimensions is PSPACE-hard:
-
-
Assumes: a polynomial number of bits of accuracy
and polynomial target time.
All previous lower bound proofs required either
artificial external forces or obstacles.
In Practice Approx. n-body Simulation is
Often Easy
l
Near linear in number of particles n:
• Can use multipole algorithms of Greengard
and Rokhlin (1985).
• Also speeded up by
John H. Reif and Steve R. Tate, "N-body simulation
I: Fast algorithms for potential field evaluation and
Trummer's problem”. (1992).
In Practice n-body Simulation is Easy
Near linear in number of particles n:
• Can use multipole algorithms of Greengard
and Rokhlin (1985).
• Also speeded up by
John H. Reif and Steve R. Tate, "N-body simulation
I: Fast algorithms for potential field evaluation and
Trummer's problem”. (1992).
Flocking: Natural “Social” Potential Field
Guided Clustering of Birds on Ground and in
Sky
• First Flocking models due to Thomas Henry
Huxley in the 1800s.
• Applied to Computer Graphics by Reynolds
(1987)
Artificial Potential Fields
• First Used in robotic motion planning
• Obstacles: provide a negative force to
object to be moved
• Not always correct solution for robotic
motion planning, but of practical use
Artificial Potential Fields
• John H. Reif and Hongyan Wang, Social
Potential Fields: A Distributed Behavioral
Control for Autonomous Robots (1994):
•
•
Workshop on Algorithmic Foundations of Robotics (WAFR'94), San Francisco, California, February, 1994;
The Algorithmic Foundations of Robotics, A.K.Peters, Boston, MA. 1995, pp. 431-459.
Published in Robotics and Autonomous Systems, Vol. 27, no.3, pp.171-194, (May 1999).
• Use n particles to represent dynamically moving
objects
• Particles may be:
• Animals
• Predators and Prey
• Robots
Artificial Potential Fields:
For distributed autonomous control of autonomous robots.
• We define simple artificial force laws between pairs of
robots or robot groups.
• The force laws are sums of multiple inverse-power
force laws, incorporating both attraction & repulsion.
• The force laws can be distinct for distinct robots - they
reflect the 'social relations' among robots.
• The resulting artificial force imposed by other robots
and other components of the system control each
individual robot’s motion.
• The approach is distributed in that the force
calculations and motion control can be done in an
asynchronous and distributed manner.
Application of Artificial Potential Fields to
Autonomous Robotic systems
•
•
•
Autonomous Robotic systems can consist of from
hundreds to perhaps tens of thousands or more
autonomous robots.
The costs of robots are going down, and the robots are
getting more compact, more capable, and more flexible.
Hence, in the near future, we expect to see many
industrial and military applications of Autonomous
Robotic systems in industrial, social, and military tasks
such as:
•
•
•
•
Organizing Group Activities such as Assembling
Transporting
Hazardous inspection
Patrolling, Guarding, and/or Attacking
Particle Systems
n Particles named 1,…,n
Each particle i=1,…,n is:
• Positioned in d-dimensional space at position Xi
• Has a current velocity Vi
• Is subject to external forces on it depending on
the arrangement of the other particles
• Has mass mk
• Obeys Newton’s laws
Inverse Power Force Laws
Example:
power law force law:
Potential Fields induced by Particle
Attraction and Repulsion
Although the inverse power laws can be complex,
the force Fi on particle i is just the sum of the
forces between particle and each other particle j:
Potential Fields induced by Particle
Attraction and Repulsion
The force Fi on particle i is the sum of the forces
between particle and each other particle j:
Potential Fields induced by Particle
Attraction and Repulsion
• ri,j = ||Xi-Xj|| is the distance between particle i
and particle j
• There is a inverse power force law Fi,j (Xi, Xj)
between particle i and particle j that depends
on distance ri,j .
• The inverse power force laws between particles
is defined by parameters ci,j and σi,j
Potential Fields induced by Particle
Attraction and Repulsion
Although the inverse power laws can be complex,
the force Fi on particle i is just the sum of the
forces between particle and each other particle j:
Clustering using an Artificial Potential Field
Initial State:
An arbitrary
Distribution of Point
Robots
The final resulting
Equilibrium State:
Uniform Clustering of
the Robots
Clustering around a “Square Castle” using an
Artificial Potential Field
Initial State:
An arbitrary
Distribution of Point
Robot Guards around
the Green Castle
Final Equilibrium State
providing Dynamic
Guarding Behavior:
The guards converge to
a guarding ring
surrounding the Green
Castle
Dynamic Guarding Behavior around a
“Square Castle” using an Artificial Potential
Field
Initial State:
An arbitrary
Distribution of Point
Robot Guards around
the Green Castle
Dynamic Guarding
Behavior:
Red Invader is
confronted by nearby
Point Robot Guards
around the Green
Castle
Reorganization of two groups (Dark and
Light Circles) before and after Bivouacking
together
Initial State:
Two separate
clusters of point
robots
Intermediate
Bivouacking State:
Merged clusters of
point robots
Final State:
Two separate
clusters of point
robots
Reorganization after Bivouacking
Clustering of Deminers (Squares) around a
Mines (Squares) using an Artificial Potential
Field
Initial State:
Separate clusters of
mines(disks) and
deminer robots (squares)
Final State:
Clusters of
deminers (squares)
near mines (disks)
Conclusion
① Artificial Potential Fields [Reif&Wang94]
provide a powerful method for programming
complex behavior in autonomous systems
② Even though in theory [Reif&Tate93] the
simulation can be hard, in practice we can use
efficient multipole algorithms
[Greengard&Rokhlin,85][Reif&Tate92] for
simulating n-body movement and predicting
the particle’s long range behavior.