On the design of minimal robots that can solve planning problems

Dylan A. Shell, Jason M. O'Kane, Fatemeh Zahra Saberifar
IEEE Transactions on Automation Science and Engineering
vol. 18
no. 3
pp. 876–887
July 2021

Abstract 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.

  author = {Dylan A. Shell and Jason M. O'Kane and Fatemeh Zahra
  journal = {IEEE Transactions on Automation Science and Engineering},
  month = {July},
  number = {3},
  pages = {876--887},
  title = {On the design of minimal robots that can solve planning
  volume = {18},
  year = {2021}

O'Kane's home page
O'Kane's publication list
Last updated 2022-09-20.