close

Вход

Забыли?

вход по аккаунту

?

Weilin Zhong, Programming Swarms

код для вставкиСкачать
Programming for Swarm
CS655 Course Project
Weilin Zhong
Swarm Computing Models
пЃ®
пЃ®
The developments in micro-fabrication and nanotechnology
will enable the inexpensive manufacturing of massive
numbers of tiny computing elements
It will become possible to build new computing models,
which incorporate large numbers of small computing
elements
April 24 2001
CS655 Project Weilin Zhong
Swarm Computing Examples
пЃ®
пЃ®
пЃ®
Intelligent and responsive environment
Multi-agent system
Amorphous computing medium
April 24 2001
CS655 Project Weilin Zhong
Swarm Computing Models
System characteristics:
пЃ®
Myriad numbers of elements.
пЃ®
Decentralized control.
пЃ®
Autonomous members behave with simple rules based on local
information, interacting with neighbors within a small radius.
пЃ®
Members collaborate to achieve sophisticated global behaviors.
пЃ®
Unreliable elements with limited power and resource connected in
irregular way.
Challenge to traditional programming models.
пЃ®
How to achieve complex global behaviors from locally information and
interaction without individually programming each member?
пЃ® System must be adaptive and self-organized.
April 24 2001
CS655 Project Weilin Zhong
Learn From the Nature
пЃ®
Social Insects
пЃ®
Nest Building
Wasp Nets
пЃ®
Ant Forage
April 24 2001
CS655 Project Weilin Zhong
What Can We Learn?
Swarm Intelligence lies on its interaction network
пЃ® Direct Interaction
пЃ® A member interacts with its neighbors
пЃ®
Indirection Interaction
пЃ®
A member interacts indirectly with other members by
changing the common environment they live.
April 24 2001
CS655 Project Weilin Zhong
Programming for Swarm
пЃ®
пЃ®
StarLogo
GPL – Growing Point Language
April 24 2001
CS655 Project Weilin Zhong
StarLogo
пЃ®
StarLogo
пЃ®
пЃ®
пЃ®
пЃ®
пЃ®
пЃ®
A Programming language and environment of decentralized multi-agent
systems.
StarLogo System consists of Turtles and Patches
Turtles are the moving agents
Patches compose the environment where the turtles live
Turtles can change the state of the patches they visit
All turtles and patches are running in parallel
April 24 2001
CS655 Project Weilin Zhong
StarLogo
пЃ®
Data Type
Booleans(true, false), Lists, Numbers, and Strings.
пЃ®
Variable
пЃ®
Building-in State Variables of turtles and patches
Xcor, ycor,color,heading,breed,shown?, pendown?
пЃ®
Global Variables
turtles own [variables]
patches own [variables]
пЃ®
Local Variables
Let [:j 0]
пЃ®
Procedure
to procedure-name
List of Commands ; no separator needed
output something ; exits and returns something
end
April 24 2001
CS655 Project Weilin Zhong
StarLogo
пЃ®
Control Flow
пЃ®
пЃ®
пЃ®
пЃ®
пЃ®
if , ifelse,
case
loop, every, repeat, do [list of commands] forever
ignore
Primitives
пЃ®
Turtle Commands
forward, bk, die
пЃ®
Patch Commands
diffuse, diffuse4, nsum, nsum4
пЃ®
Observer Commands
ca, crt, setc, setpc
ask-turtles, ask-patches,
April 24 2001
CS655 Project Weilin Zhong
StarLogo
Ant Forage Model
пЃ® Observe Procedures
Setup the nest, foods,
generate ants
Initial ants and patches
пЃ®
Turtle Procedures
Look-for-food, find-food,
return-to-nest, find-nest
пЃ®
Patches Procedures
diffuse, evaporate
April 24 2001
CS655 Project Weilin Zhong
StarLogo
Ant Forage Model
April 24 2001
CS655 Project Weilin Zhong
StarLogo
пЃ®
Advantage
пЃ®
пЃ®
пЃ®
Limitations
пЃ®
пЃ®
пЃ®
Programmable Modeling Environment for Decentralized Multi-agent
System with Massive Parallel support
Suitable for biology life simulation, traffic, economic and ecology
models
Patches are regular coordinated spatial lattice
Patches have limited computational capabilities and weak influence
to its neighborhood
Problems with the language
пЃ®
пЃ®
пЃ®
Limited number of Data Types
Parameters only passed by value
No patches command center
April 24 2001
CS655 Project Weilin Zhong
Growing Point Language
пЃ®
Amorphous Computing Medium
пЃ®
пЃ®
GPL(Growing Point Language)
пЃ®
пЃ®
is a system of irregularly placed, identically programmed,
asynchronous, locally interacting computational particles
is a language to program amorphous computing medium to generate
highly complex and prespecified patterns
A CMOS Circuit layout
пЃ®
obtained from a small program encoding about 17 computational
states
April 24 2001
CS655 Project Weilin Zhong
Growing Point Language
пЃ®
Botanical Metaphor - Growing Points and Tropisms
пЃ®
пЃ®
пЃ®
пЃ®
пЃ®
Growing Point is a lotus of activity which can propagate its activities
to its neighbors
A growing point move according to its tropism, which is specified in
terms of differences in pheromone levels in its neighborhood
A growing point can “deposit” material and “secrete” pheromone
when it visits a particle
The path of growing point is the collection of particles it have visited,
expressing by the materials it has deposited on those particles.
Theorem
пЃ®
Amorphous media can be programmed to draw any prespecified
planar graph
April 24 2001
CS655 Project Weilin Zhong
Growing Point Language
пЃ®
Primitive Datatypes
пЃ®
Materials
пЃ®
пЃ®
пЃ®
пЃ®
Pheromone
пЃ®
пЃ®
пЃ®
markers to indicate where growing points have previously visited
can be associated with a color
can be sensed by a growing points to make growth decision
exists to guide the movement of growing point
radially symmetric about the source and monotonic decreasing in the
distance from the source
Tropism Expressions
April 24 2001
CS655 Project Weilin Zhong
GPL – A-to-B segment
(define-growing-point (A-to-B)
(material A-material)
(size 0)
(tropism (ortho+ B-pheromone))
(for-each-step
(when ((sensing? B-material)
(terminate))
(default
(propagate)))))
(define-growing-point (B-point)
(material B-material)
(size 0)
(for-each-step
(secrete+ 10 B-pheromone)))
(color
((B-material) "red")
((A-material) "yellow"))
(with-locations
(a b)
(at a (start-growing-point A-to-B))
(at b (start-growing-point B-point)))
April 24 2001
CS655 Project Weilin Zhong
GPL – A-to-B Segment
April 24 2001
CS655 Project Weilin Zhong
GPL
пЃ®
Advantages
пЃ®
пЃ®
пЃ®
пЃ®
пЃ®
пЃ®
Irregular and coordinate free domain
Strict locality
Identically Programmed member
Particles compose the environment
Suitable for responsive environment and improved
materials
Facilitate the analysis of programs
April 24 2001
CS655 Project Weilin Zhong
GPL -- Limitations and Improvement
Dynamic Problem
пЃ® Limitation
Static Particles
пЃ® Static Materials and Pheromone
пЃ® Static Model
---- lack of emergence, can only generated prespecified patterns
пЃ®
пЃ®
Improvement
пЃ®
пЃ®
пЃ®
Mobile particles
Changeable Material labeling and Pheromone Evaporation Model
Dynamic and Real-time Model
April 24 2001
CS655 Project Weilin Zhong
GPL – Limitation and Improvement
пЃ®
Reliability Issues
пЃ®
пЃ®
пЃ®
Extremely Friendly Environment
Reliable Communication System
Problems and Solutions
пЃ®
пЃ®
пЃ®
Communication Error
– Error recoverable encoding, retransmission
Unreliable Particles
– Neighborhood backups
Malicious Particles
-- Redundant Computation and agreement in neighborhood
April 24 2001
CS655 Project Weilin Zhong
StarLogo and GPL
Similarity
пЃ®
пЃ®
пЃ®
пЃ®
Decentralized system consisting large number of members
Autonomous members achieve complex global behaviors
from local interaction
Massive Parallel Model
Object Oriented
Shortcomings
пЃ®
пЃ®
No consideration of security and survivability
Performance
April 24 2001
CS655 Project Weilin Zhong
StarLogo and GPL
пЃ®
StarLogo
пЃ®
пЃ®
пЃ®
пЃ®
пЃ®
Multi-agent System
Mobile agents and static
env
Regularly discrete and
coordinated spatial
system
Dynamic and adaptive
models
April 24 2001
GPL
пЃ®
пЃ®
пЃ®
пЃ®
Amorphous Computing
Medium
Static particles
Irregular coordinated free
domain
Static Models
CS655 Project Weilin Zhong
Summary
Документ
Категория
Презентации
Просмотров
2
Размер файла
390 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа