O'Reilly Emerging Technologies Conference 2003 Eric Bonabeau, icosystem Biological computing talk 2003-04-23 Notes by Dan Moniz Mindset is more important than technology - You *can* solve problems by looking from the bottom up - Whole is more than the sum of it's parts - Inspiration from nature to design computational solutions to problems Double bridge experiments (Brussels, 15 years ago) - Starve ants to get them to actually do anything - Ants set out for food - Leave pheromone trail - More ants leave, pick either unmarked trail or marked trail - Ants who go over the known route leave more pheromone - Some renegade ants may pick another path - Over time, most of the ants will go on whichever path is more marked - If paths are not equivalent (different lengths), ants will collectively select the shortest path to the food source - The short path will be marked first by the first ant - This ant goes to the food source, and returns - This is a simple (but not robust) optimization - If you offer the long path first, the colony will use that. - If you offer the short path 30 mins later, no ants will use the the short path because the long path is so highly marked - Robustness via evaporation - Pheremones evaporate over time. - Hard to maintain a stable trail to a food source if the trail is long. - Evaporation promotes shorter paths (easier to maintain) Traveling Salesman Problem - Visit each city once, find shortest tour which brings you through each city - "Three things you don't do in public, and on of them is mathematics." - Travelling sales-ants - d(sub i)(sub j) = distance between i and city j - tau(sub i)(sub j) = virtual pheromone on link (i,j) - m agents, each building a tour - At each step of a tour, the probability to go from city i to city j is proportional to (tau TK - Virtual pheremone evaporation (dependent on rate) eliminates sub-optimal solutions Dynamic factory scheduling - Production scheduling Routing in communications networks - Simple agents are launched in the network. Each agent goes from a source destination node. - An agent updates routing tables on its way to its destination, _viewing its source as a destination_ [ed: backtracking] - "If you are going toward my source node, then hop from the node I am just coming from. Or don't". - Agent influence decreases with age - Agents are artificially delayed at congested nodes - Up to 95% improvement using "AntNet" over OSPF - Unilever plant scheduling - Pina Petroli truck routing - Air Liquide supply chain optimization - British Telecom, France, etc. using it in telecom and networks Simple rules rule - Bucket brigade in harvester ants - Ants in southern Spain retrieve seeds from a source in a bucket brigade of up to six workers - First and smallest ant collects a seed from a source and starts to carry it along towards the next until it meets a larger works - The larger worker takes the seed from the ant continues to transport the seed towards the next while the smaller ant return to the source. - Taco Bell bucket brigade - The least efficient people start the task - The most efficient people finish the task - Optimal work-sharing emerges spontaneously Aggressor and defender game - Pick two people in the audience - Walk in a fashion that your defender is always in front of you and your aggressor. - Most people don't get it right, but do ridiculous - Variation: now you must keep yourself between your defender and your agressor. - It's really hard to predict what's going to happen in the aggregate, even from simple rules. - Changing the rules a little bit results in a huge impact - People won't know why they made their move decisions from the rules alone (it's intuitive), and they only give answers based on local information. - Problem (Southwest Airlines) - Optimize cargo routing - Use simple rules - Results - 71% improvement - At least $10MM/yr savings UAVs - Simple rules to enable a human operator to control UAVs. - Talk on Friday in detail about this A cautionary tale about "blindly" following simple rules - Army ants - Can destroy their environment very efficiently by mindlessly following simple rules - Follow trail - Lay trail - Circular mill in army ants: a circle of ants continuous following each other round and round until death (Schneirla). Beebe (1921) observed a mill in Guyana that measured 1200 feet in circum. with a circuit time for each ant of about 2.5 hours. The mill persisted for two days with an increasing number of dead bodies littering the trail. No one needs to be in control - Cooperative transport - Not necessarily very efficient, but intellectually satisfying - Ants push and pull large prey until chance allows them to all push or pull in the same direction. - Robots do this - Collective task completion - No need to overly complex algorithms - Adaptable to complex and changing environments - Nest construction in wasps - Building model - Agents move randomly on a 3D grid of sites - Bricks have no intelligence and only local information - [ed: looks like CA] Size matters - Water-handling task partitioning - Polyvalence - Smaller colony - Most workers do all tasks when the colony is small/young - Specialization - Larger colony - Emergent specialization as the same colony grows larger - Honeybees - S-shaped curve as a function of the number of bees - Y axis: System efficiency - X axis: System size - Slow growth, followed by explosive growth, followed by saturation - Inflection point is the middle point of the curve, the bounding points being the start and the end of the explosive growth. This is the "swarming zone". - Nature never merges, it always de-merges Swarm intelligence is obviously becoming popular - Prey by Michael Crichton - _Swarm Intelligence_, Bonabeau an author, Santa Fe Institute Coming soon - More distributed optimization/control applications - Self-healing, self-organizing comm networks - Swarm robotics will move beyond mapping - Self-aggregating devices - Self-organized satellite deployment - Controlling swarms of UAVs, UGVs, UUVs - Swarm based sensor networks, smart dust - Social engineering of collective phenomena Mail info@icosystem.com for information, articles.