Shackling Uncertainty Using Mixed Criticality in Monte-Carlo Tree Search

In the world of embedded systems, optimizing actions with the uncertain costs of multiple resources in order to achieve an objective is a complex challenge. Existing methods include plan building based on Monte Carlo Tree Search (MCTS), an approach that thrives in multiple online planning scenarios. However, these methods often overlook uncertainty in worst-case cost estimations. A system can fail to operate/function before achieving a critical objective when actual costs exceed optimistic worst-case estimates, even if replanning is considered. Conversely, a system based on pessimistic worst-case estimates would lead to resource over-provisioning even for less critical objectives. To solve similar issues, the Mixed Criticality (MC) approach has been developed in the real-time systems community. Thus we propose to extend the MCTS-based heuristic in three directions. Firstly, we reformulate the concept of MC to account for uncertain worst-case costs, including optimistic and pessimistic worst-case estimates. High-criticality tasks must be executed regardless of their uncertain costs. Low-criticality tasks are either executed in low-criticality mode utilizing resources up-to their optimistic worst-case estimates, or executed in high-criticality mode by degrading them, or discarded when resources are scarce. In such cases, resources previously devoted to low-criticality tasks are reallocated to high-criticality tasks. Secondly, although the MC approach was originally developed for real-time systems, focusing primarily on worst-case execution time as the only uncertain resource, our approach extends the concept of resources to deal with several resources at once, such as the time and energy required to perform an action. Finally, we propose (MC)<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>TS an extension of MCTS with MC concepts to efficiently adjust resource allocation to uncertain costs according to the criticality of actions. We demonstrate our approach in an active perception scenario. Our evaluation shows (MC)<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>TS outperforms the traditional MCTS regardless of whether the worst case estimates are optimistic or pessimistic.