Coverage Path-Planning

A problem studied in the field of AI planning is the coverage path-planning problem (CPP). This problem consists in finding a path that covers a given region entirely while respecting some constraints (e.g., avoid obstacles, use only simple movements, etc.), and minimizing the time of plan execution (or, e.g., the number of movements). This problem appears in several contexts, such as search and rescue, minesweeping, 3D reconstruction of regions flown over by a drone, submarine exploration using autonomous underwater vehicles (AUVs), floor or window cleaning, and 3D printing.

Unfortunately, no optimal CPP planner exist in literature (apart from the naïve exhaustive search solution). Furthermore, no CPP planner considers uncertainties, energetic constraints as well as dynamic environments. In this project, we developed a C++ CPP Library that supports classical algorithms (e.g., the wavefront algorithm) as well as our proposed new planning algorithms that uses heuristic search and branch-and-bound techniques.