Understanding the Complexity of Motion Planning through Gadgets (talk from TJCDCGGG2021)

Abstract: Most motion planning problems — designing the route for one or more agents (robots, humans, cars, drones, etc.) through a changeable environment — are computationally difficult: NP-hard, PSPACE-hard, or worse. Such hardness proofs usually consist of several "gadgets" — local pieces of environment with limited agent interactions/traversals, some of which change local state, which in turn change available interactions/traversals — that can be pasted together into the overall reduction. In this talk, I'll describe our quest to characterize exactly which such gadgets suffice to prove different kinds of hardness, in our "motion-planning-through-gadgets" framework that has developed over the past few years. This theory enables many hardness proofs, old and new, to be distilled down to a single diagram of a single gadget.

To learn more, check out the following papers/theses:

[CentralParkish]

This is more entertaining lecture than on the chalk board