Coordinating Heterogeneous Interacting Planning Agents Using Game Theory

• Applicant: Professorin Dr.-Ing. Jane Jean Kiam
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 505483373

Automated planning is commonly used for deciding a sequence of actions while anticipating their effects in view of optimizing one (or multiple) metric(s). It is often used for long- or short-term (sequential) decision making processes, for single- or multi-agent planning, and for performing causal-effect reasoning from a higher strategic level down to a lower tactical level, thereby bringing the solution closer to executable actions. On the other hand, game theoretical methods are commonly exploited at a strategic level, to compute the best strategies for optimizing stochastically an agent’s reward while considering other agents‘ strategies. Especially interesting is the use of these methods for playing against non-cooperative agents, since the majority of games involves agents with whom there is no bridge of communication (i.e. no knowledge of their strategies). Combining methods from both automated planning, including sequential decision making under uncertainty, and game theory can be beneficial, especially for solving planning problems that involve non-cooperative agents, short-term strategy choice (few decision steps) and long-term execution of actions (numerous decision steps). CHIP-GT works towards a framework to tackle this class of planning problems. To this end, game theoretical methods for non-cooperative agents and methods for automated (task and motion) planning under uncertainty are considered. The first focus of CHIP-GT is to establish a proper formalism to define and analyse the class of problems we intend to solve. This includes studying the computational complexity of the problem, and the possibility of an upscaling, i.e. feasibility of a plan repair, inclusion of more agents and modelling the agents as controllable as well as uncontrollable entities. Besides, we also work towards designing the architecture of the framework capable of combining game theoretical with automated planning methods. Specifically considered in the framework is the “acting” paradigm, which is essential for considering executabtility of plans, for new sensed information and for making flexible plan repair when necessary. Game theoretical and planning methods will be implemented as backend modules of the framework; additionally, a script-based interface as the frontend module for modelling the problem will also be developed. To illustrate the applicability of CHIP-GT, we will use Green Stochastic Games (GSG) benchmarks in which agents need to decide for strategies and plan for executable actions while considering the complex topology and uncertainty of the environment. For a more realistic validation pipeline, CHIP-GT will work with data from environmental sciences and use the typical setting of GSG-operations to build a simulator. Results obtained will be beneficial for offering insights in future works to combine both research landscapes (i.e. automated planning and game theory), and for direct reuse in GSG (e.g. biodiversity conservation).

• DFG Programme: Research Grants
• International Connection: France
• Cooperation Partners: Professorin Dr. Caroline P.C. Chanel; Dr. Régis Sabbadin