Hierarchical Influence Diagrams
Authors
Ledet, Thomas ; Kristensen, Michael Fogh
Term
4. term
Education
Publication year
2004
Abstract
I dette projekt præsenterer vi Hierarchical Influence Diagrams (HID), et rammeværk til at modellere, hvordan en agent i et spil træffer beslutninger. Et influence diagram er en grafisk model, der kobler valg, usikkerheder og mulige udfald. HID gør en kompleks model mere overskuelig ved at opdele den i mindre dele, der samles som noder i en træstruktur. Når agenten bevæger sig ned gennem træet, behøver den kun at forholde sig til information, der er relevant for den aktuelle beslutning. Når den når et bladnode i bunden, bestemmer denne node den næste HID-beslutning og dermed agentens handling. HID tilbyder to måder at gennemløbe træet på: en hændelsesbaseret algoritme og en tids-slot-baseret algoritme. Den hændelsesbaserede algoritme genanvender den tidligere valgte bladnode, hvis ingen af de oplysninger, den bygger på, har ændret sig siden sidste HID-beslutning. Ellers finder den det første sted, hvor information er ændret, og gennemløber træet på ny derfra. Den tids-slot-baserede algoritme genvurderer med jævne mellemrum den tidligere sti startende fra en bestemt node. Denne startnode vælges ud fra et brugerspecificeret planlægningsforhold, som angiver dybden for næste startpunkt. Til fremtidig afprøvning af HID og algoritmerne er der designet et bræt-lignende realtids-actionspil.
In this project, we present Hierarchical Influence Diagrams (HID), a framework for modeling how an agent in a game makes decisions. An influence diagram is a graphical model that links choices, uncertainties, and possible outcomes. HID makes a complex model easier to manage by splitting it into smaller parts that are combined as nodes in a tree. As the agent moves down the tree, it needs to consider only the information relevant to its current decision. When it reaches a leaf node at the bottom, that node determines the next HID decision and thus the agent’s action. The HID framework supports two ways to traverse the tree: an event-based algorithm and a time-slot-based algorithm. The event-based algorithm reuses the previously selected leaf node if none of the information it relied on has changed since the last HID decision; otherwise, it finds the first node where information has changed and retraverses from there. The time-slot-based algorithm periodically re-evaluates the previous path starting from a specific node chosen by a user-defined scheduling ratio that specifies the depth of the next starting point. To enable future testing of HID and these algorithms, we design a board-like real-time action game.
[This abstract was generated with the help of AI]
Documents