Swarm Intelligence and Bio-Inspired ComputingTable of ContentWhat is Biologically Inspired Algorithm?MotivationApplicationApplication in previous lectureSwarm IntelligenceAnt Colony OptimizationAnt Path AlgorithmSlide 10Slide 11Ant Traffic OrganizationSlide 13Slide 14Slide 15Terrain-Covering Ant RobotsSlide 17Theoretical FoundationAnt RobotsRestrictionAnt Robot BehaviorExperiment ResultSlide 23SimulationSimulation ResultVideoDynamic Redistribution of a Swarm of RobotsAnt house huntingSlide 29Slide 30Simple system modelSlide 32ResultSlide 34Slide 35Problem in first systemSystem with quorum sensingSlide 38Slide 39Slide 40Evolutionary ComputationSlide 42Slide 43Evolving Schooling BehaviorsThe basic behavior modelSlide 46Slide 47Slide 48ExtensionSlide 50Predator's behaviorEcologyEvolutionSlide 54Slide 55Slide 56Slide 57Result comparison with real fish schoolingSlide 59ConclusionReference2007 Fall Comp790-058 LectureSang Woo LeeWhat is Biologically Inspired Algorithm?Swarm IntelligenceEvolutionary ComputationApplication in Motion PlanningTrail-Laying Robots for Robust Terrain CoverageDynamic Redistribution of a Swarm of RobotsEvolving Schooling Behaviors to Escape from PredatorSimulate biological phenomena or modelWorking algorithm in natureProven its efficiency and robustness by natural selectionDealing too complex problemsIncapable to solve by human proposed solutionAbsence of complete mathematical modelExisting of similar problem in natureAdaptationSelf-organizationCommunicationOptimizationRoboticMulti-Robot Motion PlanningSelf-configurationNetworkDistributed autonomous systemRouting algorithmSocial OrganizationTraffic controlUrban planningComputer ImmunologyBoids in Nick’s lectureWell known flocking algorithmFlockingSeparationAlignmentCohesionMachine Learning in Dave’s lectureNeural NetworkSupervised learning MethodPopulation of simple agentsDecentralizedSelf-OrganizedNo or local communicationExampleAnt/Bee coloniesBird flockingFish schoolingMeta-heuristic OptimizationInspired from the behavior of ant coloniesShortest paths between the nest and a food sourceEvaporating pheromone trailProbabilistic path decisionBiased by the amount of pheromoneConverge to shortest pathAnt trips on shorter path returns quickerLonger path lose pheromone by evaporatingSolved problemsTraveling Salesman ProblemQuadratic Assignment ProblemJob Shop SchedulingVehicle and Network RoutingDussutour, A., Fourcassié, V., Helbing, D. & Deneubourg, J. L. Optimal traffic organization in ants under crowded conditions. Nature 428, 70-73 (2004) Research on ant path selection in bottle-neck situationMaximizing traffic volumeSymmetrical traffic in narrow pathThreshold width between 10.0 and 6.0mmPushed Ant is redirected to other pathSymmetry restored before the maximum flowBenefits of using a single trailCondensed trail - Better orientation guidance and stronger stimulusHigh-density - Good information exchangeOptimize the rate of food returnProved by analytical model and experimentJ. Svennebring and S. Koenig, “Trail-laying robots. for robust terrain coverage,”, Proc. of IEEE International Conference on Robotics and Automation 2003, Volume: 1,L On page(s): 75- 82 vol.1Inspired by Ant forageExploration & CoveragePebbles III robot6 infrared proximeterBump sensor, 2 motorsLay trails – Black pen to track trail8 Trail sensorNode CountingRobot repeated enter cellsCounting by markers in cellMove to smallest numberNo communicationVery limited sensingVery limited computing powerMarking current cellSensing markers of neighbor cellsAssumptions on theoretical foundationMove discrete stepMark cell uniformlyNo noise in sensorBy the way, it works evenUneven quality trailSome missing trailPushed to other locationObstacle Avoidance BehaviorInversely proportional to the distanceWeight for each direction sensorTrail Avoidance BehaviorFixed lengthTrail sensor with recent past informationWeight Balancing of two behaviorNeed to well balancedWork well withUneven quality trailMove another locationRemoving patches of trailFaster than random walkUntil some thresholdToo many trails result large coverage timeWith no cleaning of TrailCoverage time grow steeplyWith cleaning of TrailSame as ant pheromoneWorks good with many coverage numberA. Halasz, M. Ani Hsieh, S. Berman, V. Kumar. Dynamic Redistribution of a Swarm of Robots Among Multiple Sites, 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems.Inspired by Ant house-huntingProbability of initiating recruitment depends on the site’s qualitySuperior site scout has shorter latency to recruitRecruitment typeSummon fellow by tandem runPassive majority by transportTransport recruitment of new site triggered by population (Over the quorum)Recruitment speed difference amplified by quorum requirementCollectively distributes itself to multiple sitesPredefined proportionNo inter-agent communicationSimilar to task/resource allocationScalableUsing fraction rather than agent numberGraph GStrongly connected graphEdge Transition rate KijTransition time TijMaximum transition capacityAll agents know Graph GPropertyStabilityConvergenceTo a unique stable equilibrium pointProved analisticallyTransition in equilibrium stateFast transition makes more idle tripsExtensionInject Quorum sensingFast converge, less idle transitionAdjacent sites communicationQuorum information instantly availableTransition rate switchAbove quorum to below quorumSet to maximum transition rateStable Converges asymptoticallyProblemIncreasing quorum increase convergence speedToo big quorum make system stuck by high transition ratesInspired from the natural processes that involve evolutionGenetic algorithmEvolution strategies, evolutionary programming, genetic programmingUse a population of competing candidate solutionsReproduce and evolve themselvesEvolutionCombinationAlterationSelectionIncreases the proportion of better solutions in the populationBetter one survives!T. Oboshi, S. Kato, A. Mutoh and H. Itoh,