## 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*

2020

To appear
**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.

@article{SheOKaSab20,
author = {Dylan A. Shell and Jason M. O'Kane and Fatemeh Zahra Saberifar},
journal = {IEEE Transactions on Automation Science and Engineering},
note = {To appear},
title = {On the design of minimal robots that can solve planning problems},
year = {2020}
}

*Last updated 2020-09-23.*