Tutorial on Ant Robotics Sven Koenig University of Southern California [email protected] joint work with Jonas Svennebring, Boleslaw Szymanski, Yaxin Liu, and Craig Tovey Overview • Cheap robots Robomow – Limited capabilities (cid:127) Computation capability (cid:127) Sensing capability (cid:127) Actuation capability – Groups of robots Cye (cid:127) Fault tolerance (cid:127) Parallelism Roomba Overview (cid:127) Ant robots – Robots with limited capabilities – Robots that leave information in the terrain (cid:127) Ant robots cannot use conventional planning methods. Rather, their behavior is driven by local interactions. This can result in very robust navigation. Recommended special journal issue for further reading: AMAI special issue on Ant Robotics edited by Wagner and Bruckstein Overview (cid:127) Our motivating task is the one-time or repeated coverage of known or unknown terrain with single robots or teams of robots – Mine sweeping – Surveillance – Search-and-rescue – Guarding – Surface inspection Overview (cid:127) This topic is a bit far out. However, … (cid:127) We will touch on different areas of AI and CS – Agent coordination (swarms) – Robotics (robot architectures, ant robots, sensor networks) – Search (real-time search) – Complexity analysis of graph algorithms (cid:127) We will see several good dissertation topics. Structure (cid:127) Motivation (cid:127) Real-time search (cid:127) Results on real-time search (cid:127) Application to ant robots and results (cid:127) Serious application: smart markers Motivating Toy Task (cid:127) Guarding a museum at night – Robots (cid:127) Computation is slow (cid:127) Sensing is noisy (cid:127) Actuation is noisy (cid:127) Robots can fail – Terrain (cid:127) Terrain might be unknown initially (cid:127) Terrain can change over time First Approach (cid:127) Good location estimates - e.g. probabilities (cid:127) Path planning – e.g. POMDPs (cid:127) Explicit coordination – e.g. auctions First Approach goal location First Approach path planning Path Planning path policy generation mapping from poses to directives (“policy”) current pose distribution directive selection POMDP topological map compilation prior actuator model POMDP pose estimation prior sensor model prior distance model model learning using GROW-BW (based on Baum-Welch) sensor report motion report desired directive sensor interpretation occupancy grid [Elfes] Path Following motion generation Obstacle Avoidance raw sonar data raw odometer data motor commands Real-Time Control