Bayesian Networks in Adaptation and Optimization of Behavioral Patterns

W pracy przedstawiamy nowe metody dla probabilistycznych modeli graficznych. Pierwsza część pracy zawiera krótkie wprowadzenie do modeli graficznych w kontekście osiągniętych wyników. W ostatnim rozdziale zawarliśmy krótkie podsumowanie wraz z opisem dalszych kierunków badań. Nieodłącznym elementem rozprawy są załączone publikacje. Jednym z kluczowych wyników zawartych w niniejszej rozprawie jest algorytm optymalizacji strategii decyzyjnych w bayesowskich diagramach wpływów. Jest to problem NP-zupełny. Zaproponowany stochastyczny algorytm generuje optymalne strategie decyzyjne wykorzystując metodę przeszukiwania wzmocnioną iteracyjnym samowyżarzaniem, która stopniowo pozyskuje nowe informacje. U podstaw stworzonego algorytmu leży zaproponowana przez Chena metoda stochastycznej optymalizacji dla problemu komiwojażera (TSP). Rozszerzona wersja algorytmu została z powodzeniem zastosowana do NP-trudnego problemu uczenia struktury sieci bayesowskiej, jak i do problemu ramifikacji transportu na płaszczyźnie, który jest również NP-trudny. Wykorzystując sieci gaussowskie stworzyliśmy algorytm wyznaczający optymalne warunkowe trajektorie przejścia pomiędzy zadanymi konfiguracjami dla systemów wieloobiektowych. Opracowana metoda została wykorzystana do kontroli ruchu oraz przegrupowania formacji jednostek na płaszczyźnie. Kolejnym zastosowaniem opracowanego algorytmu jest symulacja realistycznych przejść pomiędzy animacjami postaci w wirtualnym środowisku. W środowisku wielokątnych pól Markowa zaproponowaliśmy nowy algorytm segmentacji, który wykorzystuje optymalizację dynamiki markowowskiej łącząc ideę samowyżarzania ze stochastyczną optymalizacją Chenowską, w której następujące po sobie aktualizacje segmentacji są przeprowadzane równocześnie z adaptacyjną optymalizacją lokalnej funkcji aktywności.

In this thesis, we present several new methods and algorithmic results related to probabilistic graphical models. In the first part, we present a short introduction to graphical models in the context of the thesis results. Our results are summarized and possible further research are pointed out in the last chapter. Finally, we include published papers. One of the most important result was developed for the strategy optimization in Bayesian influence diagrams. It is a well-known NP-complete problem. The proposed stochastic algorithm generates optimal decision strategies by an iterative self-annealing reinforced search procedure, gradually acquiring new information while driven by information already acquired. At the basis of the method lies the Chen-style stochastic optimization which was originally proposed for travelling salesman problems (TSP). The algorithm, after a substantial extension, is applied to the NP-hard problem of learning Bayesian network structure. Another application of the algorithm is in the NP-hard ramified optimal transport problem. In Gaussian-network set up, we develop an algorithm for determining optimal transition paths between given configurations of systems consisting of many objects. The method is applied to a system controlling the motion and redeployment between unit's formations and to a realistic transformation between two sequences of character animations in a virtual environment. Using the framework of polygonal Markov fields, we introduce an image segmentation algorithm. Our algorithm is based on the Markovian optimization dynamics combining the simulated annealing ideas with those of the Chen-style stochastic optimization - in which successive segmentation updates are carried out simultaneously with the adaptive optimization of the local activity functions.