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.

Download

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

O'Kane's home page
O'Kane's publication list

Wed Mar 4 12:52:19 EST 2020