584 stigmergy

Information about 584 stigmergy

Published on December 31, 2007

Author: Octavio

Source: authorstream.com

Content

From Local Actions to Global Tasks: Stigmergy and Collective Robotics:  From Local Actions to Global Tasks: Stigmergy and Collective Robotics R. Beckers, O.E. Holland, J.L. Deneubourg Presenter: Lewis Girod Outline:  Outline What is Stigmergy? Stigmergy in nature A robot experiment: collective pile formation Analysis and conclusions Stigmergy:  Stigmergy Stigmergy is communication by means of modifying the environment Originally used to describe behavior of nest-building termites and ant trails Paper demonstrates its power as a tool for coordination in a loosely coupled system What’s it good for?:  What’s it good for? Stigmergy is a mechanism for binding task state information to local features of a task site, and for communicating by modifying those features. Example: Following a trail: Trail markers are easy to detect, unambiguously map to location Each marker indicates the next step in following the trail Example: Termites building an arch: Two phases: column building and arch formation Pheremone deposition and diffusion processes select phase Ants need no state; simply react to pheremone concentrations Example: Referencing / returning to location Eliminate need to determine & communicate location Stigmergy in nature:  Stigmergy in nature Ant trails Ants find the shortest path to a food source in their vicinity using stigmergy to maintain traffic statistics Termite nest-building Termites build columns and arches using stigmergy to retain state about the building process Ant corpse-gathering Ants pick up dead ants and drop them in piles, preferring larger piles, until there is only one pile left Ants finding the shortest path:  Ants finding the shortest path Ants follow random paths, influenced by presence of pheremones Ants returning with food leave stronger trails Pheremones evaporate, causing frequently used trails to dominate Shortcuts result in higher traffic (more trips per ant per unit time) and thus are selected with greater probability Termites building an arch:  Termites building an arch Termites make mud balls with pheremones Termites deposit mud balls near existing pheremone concentrations As columns get taller pheremones on the bottom evaporate Pheremones on neighboring columns cause the tops to be built together to form an arch Ant corpse-gathering:  Ant corpse-gathering Scattered corpses are picked up and dropped Small piles form Gradually the piles are aggregated into a single large pile This paper describes an experiment with robots that exhibits a similar behavior. Collective pile formation task:  Collective pile formation task The robots 21x17 cm base with two wheels and a “gripper” battery powered IR sensors for obstacle detection “gripper” (really a “pusher”) force sensor Environment square arena, about 2.5x2.5 m 81 circular pucks (4 cm) arranged on a 25 cm grid The pile formation experiment:  The pile formation experiment The initial task given the robots was to push all the pucks into a single pile. At the start of an experiment, robots are in the center, oriented randomly After each 10 minute interval, the robots are stopped and sizes and positions of clusters noted Experiment ends when all pucks are in a single cluster. Robot behaviors:  Robot behaviors Very simple set of three behaviors If IR sensor active: turn away from obstacle through a random angle If force sensor active: Force sensor triggered when 3 or more pucks are pushed When sensor activates, pucks are dropped Reverse both motors for one second Then turn away to a random angle Default: Move forward until sensor activated How it works:  How it works Robots move around randomly If they bump into a puck, they will push it along. When they bump into their third puck, they drop. Initially, all piles are of size 1 Robots will pick them up and will not deposit until they have collected 3 pucks A pile of 3 or more tends to get bigger Robots that hit a pile of 3 or more head-on will add their pucks to pile. How do piles aggregate?:  How do piles aggregate? Initially, a few small clusters form quickly. Then, gradually those clusters are aggregated This occurs when pucks are stripped from the edge of a pile and then deposited elsewhere. Larger piles have a larger ratio of areas in the middle to those on the edge. Therefore probability of hitting tangent to pile decreases with pile size. Thus larger piles have a larger probability of increasing as a result of this process. Where is the stigmergy?:  Where is the stigmergy? By adding pucks to a pile, a robot makes the pile larger, and votes for that pile to be largest This stigmergically encodes a message “this is the largest pile, add more pucks to it” The strongest such message (i.e. the largest pile) wins and eventually accretes all the pucks. Because all state information is encoded in observed pile size, new robots can be added with no “communication overhead” Results:  Results The experiment was performed with varying numbers of robots Adding robots sped convergence, up to 3 robots More than three robots got in each others’ way Whenever they turn to avoid each other, they run the risk of scattering a nearby pile as they turn away Because the frequency of interactions increases with more robots, 3 was experimentally determined to be optimal Although not shown in paper, this is likely a function of robot density. Seeding clusters:  Seeding clusters Further experiments were done by seeding the environment with a heavy object This forms an initial pile that cannot be consumed Seed reliably accreted the largest pile When two seeds were used, two piles formed Never stabilized The larger seed captured most of the pucks Discussion:  Discussion Stigmergy piggybacks communication on top of robot’s existing sensing and actuation Allows system to scale to additional robots without additional communication overhead Although high densities can lead to gridlock, etc. Stigmergy stores state in the environment so that it is easily retrieved by specialized sensors In nature, pheremones In robotics, wireless communications channels

Related presentations


Other presentations created by Octavio

Moringa
28. 11. 2007
0 views

Moringa

VISCO IDN Gold WebEx
18. 04. 2008
0 views

VISCO IDN Gold WebEx

aghion pp
13. 04. 2008
0 views

aghion pp

MorganStanley 022504
10. 04. 2008
0 views

MorganStanley 022504

Temp Radn
07. 04. 2008
0 views

Temp Radn

Ed gallagher
30. 03. 2008
0 views

Ed gallagher

orozco
27. 03. 2008
0 views

orozco

Free flaps slides 051019
26. 03. 2008
0 views

Free flaps slides 051019

040605 Mob HvdB
21. 03. 2008
0 views

040605 Mob HvdB

TEAT Self study PPT 2007
18. 03. 2008
0 views

TEAT Self study PPT 2007

Funny images with music
27. 08. 2007
0 views

Funny images with music

Housing
28. 09. 2007
0 views

Housing

4050 Design Pattern
12. 09. 2007
0 views

4050 Design Pattern

strategy acquisition
12. 09. 2007
0 views

strategy acquisition

Summerhill
27. 09. 2007
0 views

Summerhill

100Ideas
06. 11. 2007
0 views

100Ideas

Argentinien
15. 11. 2007
0 views

Argentinien

Heritage
07. 10. 2007
0 views

Heritage

clinical progress
16. 11. 2007
0 views

clinical progress

undergraduate thesis defense
21. 11. 2007
0 views

undergraduate thesis defense

chap3lecture
23. 11. 2007
0 views

chap3lecture

Exercise14
14. 08. 2007
0 views

Exercise14

Maryland Exiles Rugby Club small
14. 08. 2007
0 views

Maryland Exiles Rugby Club small

LISA2001
14. 08. 2007
0 views

LISA2001

rhymes
14. 08. 2007
0 views

rhymes

PNR Meeting NovDec 2005
14. 08. 2007
0 views

PNR Meeting NovDec 2005

Solar Hot Water
09. 11. 2007
0 views

Solar Hot Water

Yihong
02. 10. 2007
0 views

Yihong

cioffidsm
28. 11. 2007
0 views

cioffidsm

TURKEY
28. 12. 2007
0 views

TURKEY

Mooney 2004
29. 12. 2007
0 views

Mooney 2004

vtls
07. 10. 2007
0 views

vtls

A Space Called School 2
03. 01. 2008
0 views

A Space Called School 2

Vote Presentation
12. 09. 2007
0 views

Vote Presentation

Lenin
14. 12. 2007
0 views

Lenin

act1
07. 01. 2008
0 views

act1

aish
03. 08. 2007
0 views

aish

Embryo Jayan Goa
01. 10. 2007
0 views

Embryo Jayan Goa

memory jungle
14. 08. 2007
0 views

memory jungle

DixieAlley megams
05. 10. 2007
0 views

DixieAlley megams

110Ch02
12. 09. 2007
0 views

110Ch02

diggov email geospatial
12. 09. 2007
0 views

diggov email geospatial

8591
25. 12. 2007
0 views

8591

lerman review
04. 01. 2008
0 views

lerman review

Samsung
19. 02. 2008
0 views

Samsung

Tao Jiang NHC2005
24. 02. 2008
0 views

Tao Jiang NHC2005

Fisher CVN 21
06. 03. 2008
0 views

Fisher CVN 21

Tema11
20. 11. 2007
0 views

Tema11

BalamInfoPrescompres sed
14. 08. 2007
0 views

BalamInfoPrescompres sed

Leaders Summit Spring 2007
11. 12. 2007
0 views

Leaders Summit Spring 2007

Vietnam1
28. 12. 2007
0 views

Vietnam1

rtdsofts
07. 11. 2007
0 views

rtdsofts

Bo Diddly Bop
12. 09. 2007
0 views

Bo Diddly Bop

Greenleaf
29. 11. 2007
0 views

Greenleaf

The Deaths of 2006
17. 06. 2007
0 views

The Deaths of 2006

sps0501
17. 06. 2007
0 views

sps0501

Sport SHOW
17. 06. 2007
0 views

Sport SHOW

sms banking demo
17. 06. 2007
0 views

sms banking demo

CPS Oct 4 2004 RBSb
07. 12. 2007
0 views

CPS Oct 4 2004 RBSb

years 5 to 12
14. 08. 2007
0 views

years 5 to 12

balta
23. 11. 2007
0 views

balta

aas asif jan02
13. 11. 2007
0 views

aas asif jan02

Fichner Rathus CH15
01. 11. 2007
0 views

Fichner Rathus CH15

stallone accardo pantaleo
17. 06. 2007
0 views

stallone accardo pantaleo

Nova
02. 01. 2008
0 views

Nova

adato fordham seminar
21. 11. 2007
0 views

adato fordham seminar

gray
04. 03. 2008
0 views

gray

200303 RiskMgmt TVera
14. 08. 2007
0 views

200303 RiskMgmt TVera

PubForum Tritsch TSInternals
16. 11. 2007
0 views

PubForum Tritsch TSInternals