Automated Planning for Task-Based Cyber-Physical Systems under Multiple Sources of Uncertainty

Abstract

In smart Cyber-Physical Systems (sCPS), a critical challenge lies in task planning under uncertainty. There is a broad body of work in the area with approaches able to individually deal with different classes of constraints (e.g., ordering, structural) and uncertainties (e.g., in sensing, actuation, latencies). However, these uncertainties are rarely independent and often compound, affecting the satisfaction of goals and other system properties in subtle and often unpredictable ways. According to the Uncertainty Interaction Problem recently proposed in the literature, approaches are needed to identify multiple sources of uncertainty and quantify their impact. In this paper we deal with two types of uncertainty present in task-based sCPS, namely temporal availability constraints and element reliability. The former refers to the availability of a given system element required to perform a task, which may be unavailable for certain periods of time, while the latter is related to system elements that may fail at some point with some probability. This paper presents an approach to consider both uncertainties, employing genetic algorithms to incorporate them effectively into planning for deciding how to best adapt the system to changes at run time. Our method is evaluated in the domains of electric vehicle charging and healthcare robotics. Our evaluation shows that: (i) the proposed approach outperforms a baseline mixed-integer linear programming (MILP) algorithm capable of generating optimal solutions in the absence of uncertainty, providing more robust solutions to failures, changes in temporal availability, or both sources of uncertainty combined; (ii) both sources of uncertainty have a strong and compound impact on the quality of the solutions provided; and (iii) the proposed approach significantly reduces computational cost, with respect to the MILP-based optimization.