Time-critical interactive dynamic influence diagram

• Propose a new decision model for solving time-critical multiagent decision making problems.
• Present an effective method to construct the model.
• Propose two methods to solve the model.
• Experiment the methods in three problem domains.

Multiagent time-critical dynamic decision making is a challenging task in many real-world applications where a trade-off between solution quality and computational tractability is required. In this paper, we present a formal representation for modelling time-critical multiagent dynamic decision problems based on interactive dynamic influence diagrams (I-DIDs). The new representation called time-critical I-DIDs (TC-IDIDs) represents space-temporal abstraction by providing time-index to nodes and the model is defined in terms of the condensed and deployed forms. The condensed form is a static model of TC-IDIDs and can be expanded into its dynamic version. To facilitate the conversion between the two forms, we exploit the notion of object-orientation design to develop flexible and reusable TC-IDIDs. The difficulty on expanding TC-IDIDs is to select a proper time sequence to index nodes in the condensed form so that the expanded TC-IDIDs can be solved efficiently without compromising the quality of the policy. For this purpose, we propose two methods to build the condensed form of TC-IDIDs. We evaluate the solution quality and time complexity in three well-studied problems and provide results in support.