Download PDFOpen PDF in browser

The hardness of minimizing design cost subject to planning problems

EasyChair Preprint no. 743

16 pagesDate: January 22, 2019


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.

Keyphrases: complexity, Planning problem, Robot design cost

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Fatemeh Zahra Saberifar and Jason M. O'Kane and Dylan A. Shell},
  title = {The hardness of minimizing design cost subject to planning problems},
  howpublished = {EasyChair Preprint no. 743},
  doi = {10.29007/h1kv},
  year = {EasyChair, 2019}}
Download PDFOpen PDF in browser