## The hardness of minimizing design cost subject to planning problems

Fatemeh Zahra Saberifar, **Jason M. O'Kane**, Dylan A. Shell

In *Proc. International Workshop on the Algorithmic Foundations of Robotics*

2018
**Abstract**
Assuming one wants to design the most cost-effective robot for some task,
how difficult is it to choose the robot's actuators? This paper
addresses that question in algorithmic terms, considering the problem of
identifying optimal sets of actuation capabilities to allow a robot to
complete a given task. We consider various cost functions which model
the cost needed to equip a robot with some capabilities, and show that
the general form of this problem is NP-hard, confirming what many perhaps
have suspected about this sort of design-time optimization. As a result,
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.

@inproceedings{SabOKaShe18,
author = {Fatemeh Zahra Saberifar, Jason M. O'Kane and Dylan A. Shell},
booktitle = {Proc. International Workshop on the Algorithmic Foundations of
Robotics},
title = {The hardness of minimizing design cost subject to planning problems},
year = {2018}
}

*Last updated 2021-07-20.*