20/07/2024

Contenus

Toggle

## Hidden Markov Model Project: Terminator

This project requires knowledge of Markov chains, automatons, and the Hidden Markov Model in order to be able to realize it.

“Is there a way to learn stuff programmatically at home, so you can look…more human…not look so dumb anymore.
- My UPC is a neuro-processor, a computer to learn, the more I have contact with humans, the more I learn.
- Cool.

## Beginning of the project

Robotics is a multidisciplinary field of study, calling on all the skills and qualities of the various ESILV majors. Robots refer to stochastic behavioral models, these are generally stochastic automata as seen in class. We will put your knowledge into practice in order to better understand how a self-learning process takes place.

A robot produced new movement behaviors in a maze. Being the first time that it encounters this type of obstacle, the robot recorded these different adventures in the heart of the labyrinth in order to learn a algorithm to get out more easily.

The robot denotes by the symbol going straight to the next wall or intersection; by b turning to the right; by c turning around. Here are the different paths he took to get out of the labyrinth (intentionally short and "illogical" but easier to work by hand):

• For 1000 attempts in the labyrinth
• 500 successes on aaba
• 100 successes on aabc
• 50 successes on aba
• 25 success stories on abc
• 25 success stories on bab
• 75 successes on caa
• 200 successes on caaab
• 25 success stories on caab
• Some actions have always led to failures
• ac
• cb
• CC
1. Represent the problem with a tree frequency prefixes
2. Reduce by Merge & Fold and ALERGIA with an alpha of 0.1 (beware of forbidden words). If the automaton does not reduce, ignore frequencies.
3. Transform the reduced automaton into HMM
4. Give the probabilities of emitting the ac, cb, cc symbol strings as well as the most probable hidden state sequence of emitting each of the symbol strings (Backward-Forward and Viterbi). You can do it by hand or by sklearn.