Optimization of information structures in influence diagrams

Abstract

Since mid 1980s, influence diagrams have been used widely in decision analysis. Traditionally, influence diagrams have a predetermined structure and the no-forgetting property, which means that earlier decisions can be recalled when making later decisions. The main focus in the literature on influence diagrams has been on determining the optimal decision strategy for an influence diagram with a given structure. However, the information structure of an influence diagram, i.e. what information should be acquired to support decisions, has attracted far less attention.

In this thesis, we examine what information should be available to the decision maker. We present optimization models for the information structure and the decision strategy of an influence diagram. The first optimization model enforces constraints on path probabilities, the second on local decisions and the third is based on the formulation of an extended state space. All models are tested with a variety of modified oil wildcatter problems and N-M-monitoring problem. The constraints on local decisions are clearly the fastest with all problem sizes. The constraints on path probabilities and the constraints on extended state space are also applicable to similar problems but they are clearly slower than the constraints on local decisions. The approaches worked for relatively large instances, but the limitations of the methods become apparent when the size of a problem is grown.

Vaikutuskaavioita on jo 80-luvulta asti laajasti käytetty päätösanalyysissä. Ne tarjoavat hyvän työkalun monivaiheisten epävarmuuksia sisältävien päätösongelmien jäsentämiseen ja ratkaisemiseen. Aiemmassa tutkimuksessa on erityisesti tarkasteltu päätösstrategian optimointia. Tässä diplomityössä keskitytään sen sijaan vaikutuskaavion informaatiorakenteen optimointiin. Pyrkimyksenä on optimaalisen päätösstrategian lisäksi optimoida tieto, jota tarjotaan päätöksen tueksi.

Vaikutuskaavion informaatiorakenteen optimointiin esitetään tässä työssä kolme optimointimallia. Yksi optimointimalleista asettaa rajoituksia polkutodennäköisyyksille päätöksen tueksi valitun tiedon mukaan. Toinen optimointimalli asettaa rajoituksia paikallisille päätöksille valitun tiedon mukaan. Kolmas optimointimalli hyödyntää laajennettua tilajoukkoa solmuille, jotka eivät välttämättä ole käytössä päätöksiä tehdessä.

Kaikkia malleja on testattu erinäisillä esimerkkiongelmilla. Malleilla ratkaistiin perinteinen öljynetsintäongelma useilla raporttivaihtoehdoilla, sekä niin kutsuttu N-M-monitorointiongelma. Testeissä havaittiin yhden mallin toimivan muita paremmin. Rajoitukset paikallisille päätöksille ratkaisivat lähes kaikki ongelmat nopeimmi. Rajoitukset polkutodennäköisyyksille ja rajoitukset laajennetulle tilajoukolle toimivat vaihtelevasti. Kaikkia malleja pystyttiin soveltamaan useita päätöksiä ja raportteja sisältäviä ongelmiin.