Download PDFOpen PDF in browser

The hardness of minimizing design cost subject to planning problems

EasyChair Preprint 743

16 pagesDate: January 22, 2019

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.

Keyphrases: Planning problem, Robot design cost, complexity

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