Bayesian Networks in Adaptation and Optimization of Behavioral Patterns
Michał Matuszak · 2013
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.