Difference between revisions of "Simulation of semi-intelligent algae"

From Simulace.info
Jump to: navigation, search
(Blanked the page)
(Tag: Blanking)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
= Introduction =
 +
This Netlogo simulation aims to copy the behaviour of a symbiotic organism called physarum polycephalum. Physarum is actually a single cell organism, but when two or more cells meet, their membranes merge together and they work together to efficiently gather nutrition and multiply.
 +
This simulation should mimic the spread and path creation of the algae, as well as its ability to solve the shortest path problem.
 +
Video about physarum: [https://www.youtube.com/embed/HyzT5b0tNtk]
  
 +
=Problem definition=
 +
The algae works in two modes: food search and optimisation. The food search part involves the algae spreading in a outward pattern, until it finds a foodsource. When it succeeds, it optimizes its pathways to allow for fastest nutrient transport.
 +
The goal is for the algae to be able to find the shortest path to food source (and optimize - destroy/recontruct exisiting pathways). It should be able to work around obstacles as well.
 +
 +
=== Software ===
 +
 +
Simulation is created using Netlogo 6.0.2.
 +
 +
= Model =
 +
 +
=== Turtles ===
 +
The agents in our simulation are three by count.
 +
 +
==== Foods ====
 +
Foods are agents that stand for foodbits in a petri dish. They are not found at first, until an algae steps on them by chance and sets their patch color from blue to green. This means that the food is now found. There is an exception however, the middle food is found from the beginning, as an inital food source for the living algae.
 +
 +
==== Algae ====
 +
These agents are there to simulate algae spread. They dont simulate the whole area of the algae, that would be too expensive and inconvenient. Instead they stand as spreading tendrils of the algae. They color new patches yellow, which means the actual algae area. Their movement is random, although they only turn in random directions by 40°. This number seems to simulate the outward, radial pattern that the algae uses to find new food. It also creates nice veiny, fractal patterns.
 +
 +
They are hatched on green spots (the food that has been discovered). They have a limited time to live, whenever they step on a new non-yellow  tile, it is lowered. This makes sure that there are no tendrils separated from the main body, just like in reality, separated algae cells would die without a food source.
 +
 +
==== Collectors ====
 +
Collectors are agents represented by blue arrows. Their task is to optimize the algae. They do so by travelling from food to food and increasing the popularity variable of each yellow patch they step on.
 +
 +
== Controls ==
 +
=== Setup ===
 +
The setup button prepares the simulation environment. First the foods are distributed at preset coordinates. They are represented by static agents with their patch initially colored blue. Further foods can also be placed manually. Secondly the algae agents are hatched from the initial green food node and start their spread. Thirdly collectors are created at green spots as well.
 +
 +
=== Go ===
 +
 +
to go
 +
  make-collectors n-collectors
 +
  make-algae physarums
 +
  make-step
 +
  move-collectors
 +
  decay-popularity
 +
  draw-turtles
 +
  tick
 +
  end
 +
 +
The simulation runs in ticks. The go button enables the repetition of several steps. First you may notice it creates collectors and algae again. This is enable the user to change the number of the agents and to recreate them in case they die. Then both agents make their move. They always move by one patch.
 +
Decay popularity class lowers the popularity variable of all yellow patches, this makes the unused paths decay. Any patches whose popularity decayed too much are recolored to pcolor 39.
 +
Draw turtles class checkes whether the user wants to show the turtles or not.
 +
 +
=== Draw walls and food ===
 +
These buttons allow the user to draw walls and new foods. The button has to be pressed, then you can draw and then it has to be unpressed again. This is because the simulation is in ticks, thus the simulation has to make a new tick to redraw the simulation. The delete walls button works the same way, except it deletes walls.
 +
 +
=== Popularity decay rate ===
 +
This slider sets the speed at which yellow patches decay. For difficult simulations with walls, it is optimal to set it lower (2-3). In an easy scenario, higher settings make the algae optimize quickly.
 +
 +
=== Algae ttl ===
 +
This sets a time to live for the algae tendril agents. High values allow the algae to spread further. Easy scenarios withouth walls are better set lower, to allow nice contrasting patterns of the algae.
 +
 +
=== N collectors and physarums ===
 +
These set the number of collector and algae agents. Higher settings are optimal for difficult scenarios. Lower settings look better.
 +
 +
=== Draw agents ===
 +
This boolean turns off or on the display of agents.
 +
 +
= Method =
 +
The algae agents are quick to find new food sources despite their random movement. The fact that they are spawned from the new foodsources soon after they are found ensures that a path is quickly built. Their limited time to live ensures that they do not wander too far from their foodsources and disconnect from the main body of the algae.
 +
 +
Collectors move in a much more sophisticated way. Their logic is that they represent the flow of nutrients through the body of the algae. This is how Physarum discerns the location of foods. Thus the collectors travel between foods and refresh the popularity of the yellow patches, ensuring that the food efficient tendrils stay alive.
 +
 +
Collectors use the class best way to to determine the direction of movement.
 +
 +
to-report best-way-to [ destination ]
 +
  set collector-vision-dist  30
 +
  let visible-patches patches in-radius collector-vision-dist
 +
  let visible-routes visible-patches with [ pcolor = 45]
 +
  let brown-routes visible-patches with [ pcolor = 39]
 +
  let routes-that-take-me-closer visible-routes with [
 +
    distance destination < [ distance destination - 1 ] of myself
 +
  ]
 +
  let brown-routes-that-take-me-closer brown-routes with [
 +
    distance destination < [ distance destination - 1 ] of myself
 +
  ]
 +
  let x routes-that-take-me-closer with [not member? self brown-routes]
 +
  ifelse any? x [
 +
    report min-one-of x [ distance self ]
 +
  ] [
 +
    report destination
 +
  ]
 +
 +
end
 +
 +
This makes the collectors travel between food nodes in shortest paths. However, this also make them connect the foods all-with-all, which isnt the solution that we want. So, in the class move-collectors we make them choose the closest food out of the foods they haven't yet visited. Netlogo was never designed to work with lists filled with agents, so this is rather complex process.
 +
 +
=Results=
 +
The random radial spread of the algae was copied appropriately. It shows how Physarum Polycephalum manages to find new food sources.
 +
 +
[[File:xvegm00-algae1.jpg]]
 +
 +
Collectors simulate the flow of nutrients and optimize the pathways correctly. They allow for constant optimization even in case of sudden changes to the topology. Given enough time, they deal with walls and adapt.
 +
 +
[[File:xvegm00-algae2.jpg]]
 +
 +
=Conclusion=
 +
The behaviour of Physarum Polycephalum can be recreated even inside such a simple simulation environment that is netlogo. It shows how the algae is able to find food even without any meaningful sensory or neural organs, simply through its "programming". The ability of the agents to find the shortest path can be considered an emergent property of the weak type. However, difficult obstacles can be a problem for the turtles to solve. This is because the pathing algorithm that is used doesn't take into calculation the obstacles. They are crossed through random tries and often cause the collectors to get stuck for some time. Improving on this problem would require a sophisticated pathing algorithm such as A* or Djikstra, which would defeat the purpose of the simulation.
 +
=Code=
 +
[[File:Semestralka.nlogo]]

Latest revision as of 11:03, 23 January 2019

Introduction

This Netlogo simulation aims to copy the behaviour of a symbiotic organism called physarum polycephalum. Physarum is actually a single cell organism, but when two or more cells meet, their membranes merge together and they work together to efficiently gather nutrition and multiply. This simulation should mimic the spread and path creation of the algae, as well as its ability to solve the shortest path problem. Video about physarum: [1]

Problem definition

The algae works in two modes: food search and optimisation. The food search part involves the algae spreading in a outward pattern, until it finds a foodsource. When it succeeds, it optimizes its pathways to allow for fastest nutrient transport. The goal is for the algae to be able to find the shortest path to food source (and optimize - destroy/recontruct exisiting pathways). It should be able to work around obstacles as well.

Software

Simulation is created using Netlogo 6.0.2.

Model

Turtles

The agents in our simulation are three by count.

Foods

Foods are agents that stand for foodbits in a petri dish. They are not found at first, until an algae steps on them by chance and sets their patch color from blue to green. This means that the food is now found. There is an exception however, the middle food is found from the beginning, as an inital food source for the living algae.

Algae

These agents are there to simulate algae spread. They dont simulate the whole area of the algae, that would be too expensive and inconvenient. Instead they stand as spreading tendrils of the algae. They color new patches yellow, which means the actual algae area. Their movement is random, although they only turn in random directions by 40°. This number seems to simulate the outward, radial pattern that the algae uses to find new food. It also creates nice veiny, fractal patterns.

They are hatched on green spots (the food that has been discovered). They have a limited time to live, whenever they step on a new non-yellow tile, it is lowered. This makes sure that there are no tendrils separated from the main body, just like in reality, separated algae cells would die without a food source.

Collectors

Collectors are agents represented by blue arrows. Their task is to optimize the algae. They do so by travelling from food to food and increasing the popularity variable of each yellow patch they step on.

Controls

Setup

The setup button prepares the simulation environment. First the foods are distributed at preset coordinates. They are represented by static agents with their patch initially colored blue. Further foods can also be placed manually. Secondly the algae agents are hatched from the initial green food node and start their spread. Thirdly collectors are created at green spots as well.

Go

to go
 make-collectors n-collectors
 make-algae physarums
  make-step
  move-collectors
 decay-popularity
 draw-turtles
 tick
 end

The simulation runs in ticks. The go button enables the repetition of several steps. First you may notice it creates collectors and algae again. This is enable the user to change the number of the agents and to recreate them in case they die. Then both agents make their move. They always move by one patch. Decay popularity class lowers the popularity variable of all yellow patches, this makes the unused paths decay. Any patches whose popularity decayed too much are recolored to pcolor 39. Draw turtles class checkes whether the user wants to show the turtles or not.

Draw walls and food

These buttons allow the user to draw walls and new foods. The button has to be pressed, then you can draw and then it has to be unpressed again. This is because the simulation is in ticks, thus the simulation has to make a new tick to redraw the simulation. The delete walls button works the same way, except it deletes walls.

Popularity decay rate

This slider sets the speed at which yellow patches decay. For difficult simulations with walls, it is optimal to set it lower (2-3). In an easy scenario, higher settings make the algae optimize quickly.

Algae ttl

This sets a time to live for the algae tendril agents. High values allow the algae to spread further. Easy scenarios withouth walls are better set lower, to allow nice contrasting patterns of the algae.

N collectors and physarums

These set the number of collector and algae agents. Higher settings are optimal for difficult scenarios. Lower settings look better.

Draw agents

This boolean turns off or on the display of agents.

Method

The algae agents are quick to find new food sources despite their random movement. The fact that they are spawned from the new foodsources soon after they are found ensures that a path is quickly built. Their limited time to live ensures that they do not wander too far from their foodsources and disconnect from the main body of the algae.

Collectors move in a much more sophisticated way. Their logic is that they represent the flow of nutrients through the body of the algae. This is how Physarum discerns the location of foods. Thus the collectors travel between foods and refresh the popularity of the yellow patches, ensuring that the food efficient tendrils stay alive.

Collectors use the class best way to to determine the direction of movement.

to-report best-way-to [ destination ]
 set collector-vision-dist  30
 let visible-patches patches in-radius collector-vision-dist
 let visible-routes visible-patches with [ pcolor = 45]
 let brown-routes visible-patches with [ pcolor = 39]
 let routes-that-take-me-closer visible-routes with [
   distance destination < [ distance destination - 1 ] of myself
 ]
 let brown-routes-that-take-me-closer brown-routes with [
   distance destination < [ distance destination - 1 ] of myself
 ]
 let x routes-that-take-me-closer with [not member? self brown-routes]
 ifelse any? x [
   report min-one-of x [ distance self ]
 ] [
   report destination
 ]
end

This makes the collectors travel between food nodes in shortest paths. However, this also make them connect the foods all-with-all, which isnt the solution that we want. So, in the class move-collectors we make them choose the closest food out of the foods they haven't yet visited. Netlogo was never designed to work with lists filled with agents, so this is rather complex process.

Results

The random radial spread of the algae was copied appropriately. It shows how Physarum Polycephalum manages to find new food sources.

Xvegm00-algae1.jpg

Collectors simulate the flow of nutrients and optimize the pathways correctly. They allow for constant optimization even in case of sudden changes to the topology. Given enough time, they deal with walls and adapt.

Xvegm00-algae2.jpg

Conclusion

The behaviour of Physarum Polycephalum can be recreated even inside such a simple simulation environment that is netlogo. It shows how the algae is able to find food even without any meaningful sensory or neural organs, simply through its "programming". The ability of the agents to find the shortest path can be considered an emergent property of the weak type. However, difficult obstacles can be a problem for the turtles to solve. This is because the pathing algorithm that is used doesn't take into calculation the obstacles. They are crossed through random tries and often cause the collectors to get stuck for some time. Improving on this problem would require a sophisticated pathing algorithm such as A* or Djikstra, which would defeat the purpose of the simulation.

Code

File:Semestralka.nlogo