Motion Planning with Guaranteed Problem Space Coverage in Semi-Static Environments
Motion planning in static environments typically involves computing a single feasible path from start to goal, as the environment remains unchanged. In semi-static environments, obstacle positions may vary between queries, but most methods solve each instance from scratch without exploiting this repeatability. Experience-based planners attempt to accelerate planning by retrieving previously computed solutions, but they lack formal guarantees and often fail to generalize to unseen or significantly different obstacle arrangements. Preprocessing-based approaches that offer fixed-time planning guarantees do exist, but they rely on discretization of the obstacle arrangement space and assume uniformity in obstacle geometry—the latter often inducing non-solvable problem instances.
In this work, we formalize the notion of problem space coverage in semi-static environments and propose an incremental planning approach that guarantees it. Our method constructs a roadmap by iteratively selecting and solving segregated problem instances to converge toward complete coverage, without the aforementioned limitations. The resulting roadmap ensures that a solution can be retrieved for any valid obstacle configuration without additional planning. We also introduce a verification tool that tests whether a given roadmap satisfies problem space coverage, and returns unsolved problem instances when coverage is incomplete. Finally, we analyze trade-offs in preprocessing time and path quality across varying queries, and demonstrate the practical benefits of our method over the constant-time motion planning baseline.
Advisor: Professor Constantinos Chamzas (WPI)
Committee: Professor Kevin Leahy (WPI) and Professor Griffin Tabor (WPI)