Shortcut through an evil door: Optimality of correct-by-construction controllers in adversarial environments
Gangyuan Jing, Rüdiger Ehlers, Hadas Kress‐Gazit · 2013
A recent method to obtain correct robot controllers is to automatically synthesize them from high-level robot missions that are specified in temporal logic. In this context, we aim for controllers that are optimal, i.e., do not let the robot take unnecessarily costly paths to reach its goals. Previous work on obtaining optimal synthesized robot controllers either ignored interactions with the environment, or assumed a cooperative environment. In this paper, we solve the problem of obtaining optimal robot controllers for adversarial environments. Our main observation is that the quality of a path to a goal has two dimensions: (1) the number of phases in which the robot waits for the environment to perform some actions and (2) the cost of the robot's actions to reach the goal. Our synthesis algorithm can take any prioritization over the possible cost combinations into account, and computes the optimal strategy in a symbolic manner, despite the fact that the action costs can be non-integer. We show the scalability of the new algorithm by example of a delivery problem.