The hardness of minimizing design cost subject to planning problems

Fatemeh Zahra Saberifar, Jason M. O'Kane and 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}
}


O'Kane's home page
O'Kane's publication list
Last updated 2024-03-28.