On the Design of Minimal Robots That Can Solve Planning Problems

摘要

This article examines the selection of a robot’s actuation and sensing hardware to minimize the cost of that design while ensuring that the robot is capable of carrying out a plan to complete a task. Its primary contribution is in the study of the hardness of reasonable formal models for that minimization problem. Specifically, for the case in which sensing hardware is held fixed, we show that this algorithmic design problem is NP-hard even for particularly simple classes of cost functions, confirming what many perhaps have suspected about this sort of design-time optimization. We also introduce a formalism, based on the notion of label maps, for the broader problem in which the design space encompasses choices for both actuation and sensing components. As a result, for several questions of interest, having both optimality and efficiency of solution is unlikely. However, we also show that, for some specific types of cost functions, the problem is either polynomial-time solvable or fixed-parameter tractable. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Note to Practitioners</i> —Despite the primary results being theoretical and, further, taking the form of bad news, this article still has considerable value to practitioners. Specifically, assuming that one has been employing heuristic or approximate solutions to robot design problems, this article serves as a justification for doing so. Moreover, it delineates some circumstances in which one can, in a sense, do better and achieve genuine optima with practical algorithms.