Transcript PPT
Cooperative Behavior & Path Planning for Autonomous Robots Lakshmanan Meyyappan (Laks) Bird’s Eye View Overview Motivation The Scavenging process Experimental Setup Fuzzy Clustering Evolutionary Algorithm Barbarian. Middle and Modern Age Crossover & Mutation The Twin Problem Results & Research Findings Future Work Overview … Scavenging process To program the robot to collect objects randomly distributed in an open terrain Assumptions: Static environment Aerial picture of the entire terrain is available Overview Aerial Picture Image processing Object Locations Fuzzy Clustering Robots in Action Optimum Path Evolutionary Algorithm Computer Motivation Scavenging Robots are useful for Collecting samples from chemically hazardous locations Landmine removal Exploring unknown regions Collecting rock samples from other planets Assembly line robots The Evolutionary Programming with some modifications can be used in a number of other areas – network routing, school bus routing, drilling holes in a circuit board …. The Scavenging Process The area is too small to fit large number of objects Evolutionary Algorithm not very efficient The Experimental Setup 360 X 160 Matrix (Football field size – 360 X 160 Feet) Random 0’s & 1’s (limiting 1’s to less than 5% in average) 1’s are the objects to be collected 1 1 160 R R 1 1 1 360 R 1 R Fuzzy Clustering Time Saving: N objects present Search space N! M clusters Then search space becomes (N/M)! If N is large (N/M)!<<N! 4 Robots – 4 clusters Better results than manual clustering Evolutionary Algorithm To find the shortest path for the four robots Overlook: The Barbarian Age The Middle Age The Modern Age Selection: Rank Based Elitist (50%) Operations: Co evolution Crossover Mutation The Barbarian Age Random population created Example: 1-2-3-4-5 (for 5 objects) Environment in total chaos (Middle of thick Chinese forest) No parent selection & No crossover Co evolution takes place Entire population mutates The shift register mutation 1-2-3-4-5 5-1-2-3-4 Starting point optimization 4-5-1-2-3 During each cycle (total number of cycle less than N), the fittest population (shortest path) are pooled together After N cycles, the pooled population is moved to a separate location (Netherlands) – The Middle age The Middle Age Rigid classification Royal family, Knights, Working Class, Slaves All are allowed to breed, but only within their class Helps in finding quick local optimums Crossover & Mutation takes place (discussed later) The fittest population after a set number of cycles is pooled and moved to the land of opportunities (USA) – The Modern age Modern Age No class differentiation No restrictions on who breeds with who Avoids locking into local minima Produces exotic results Kristin Kreuk Dutch father Chinese Mother Born in Canada Now in USA Crossover The Greedy Crossover Example Parent 1: Parent 2: 1-2-3-4-5 4-1-3-2-5 2 Child: 1 4 1-3 3 3 1-3-2 2 1-3-2-5-4 5 Mutation The chance of mutation reduces with civilization (Barbarian-Middle-Modern) Example Route: 1-2-3-4-5 Attempt 1: 2-1-3-4-5 Attempt 2: 3-2-1-4-5 Attempt 3: 4-2-3-1-5 Attempt 4: 5-2-3-4-1 The shortest of the four routes is chosen as the mutated offspring The Twin Problem If any two child resemble each other (same route), they are called twins Twins are of no use to us as they represent the same routes Hence Dr. T, The Terminator is called Dr. T, terminates one of the twin and replaces it with a random child Results – So Far… No. of Objects 150 300 600 Time 2.5 7 16 Random 1000-1488 2300-3132 3228-4320 Barbarian Mutation 900-1082 2102-2510 3093-3486 Middle Age Crossover 400-547 502-626 764-999 Middle Age Mutation 400-494 492-580 720-860 Modern Age Crossover 313-337 440-474 560-592 Modern Age Mutation 313-333 435-460 555-578 Research Findings Time advantage Is this the optimal solution? Theoretical advantage Much faster than a random search or heuristic search Clustering helps in avoiding robot clashes Mutation operator is not very good Future Work Have a dynamic environment Eliminate image processing Rephrase the problem to make comparisons with available TSP datasets & solutions Hey What Do Ya Think Any Questions?