S&AS: FND: Long-Term Planning and Robust Plan Execution for Multi-Robot Systems

University Of Southern California, Los Angeles CA

Investigators

Abstract

How can multi-robot teams maneuver in tight and cluttered environments when "no plan survives contact" with reality? Traditional approaches plan for idealized situations and must patch up maneuvers when sensors or actuators are imprecise, making them neither robust nor safe. This project, a collaboration of PIs from artificial intelligence and robotics, will investigate fundamental research to capture and use timing and uncertainty constraints in large robot navigation and coordination problems. The target applications are just-in-time manufacturing and automated warehousing, but the results will extend beyond to many applications of smart and autonomous systems that need reliable and safe planning. The project will study Multi-Agent Path Finding (MAPF), which is an NP-hard planning problem that belongs to a class of important planning problems, namely multi-agent navigation problems with temporal and spatial constraints. The research will relax simplifying assumptions typically made by MAPF solvers, namely that plan execution is perfect and stops once all robots have reached their goal locations. Many AI planning methods that have been developed are not used on robots, since planning/scheduling uses idealized models of the environment and plan execution is never perfect, and there is often insufficient time for re-planning if execution deviates from the plan. This project will develop well-founded planning and plan-execution methods, based on probabilistic and temporal reasoning, that fuse ideas from robotics and artificial intelligence. In particular, the PIs will combine advances in planning algorithms from the AI community, namely Simple Temporal Networks (STN), and adapt them to the robotics domain by adding timely execution constraints, as well as sensor, actuator, and model uncertainties. They will make project results (such as papers, videos and code) available on their web pages, present tutorials on their research results to the artificial intelligence and robotics research communities, develop teaching material for multi-robot planning, and integrate undergraduate students into their research activities.