Application of MCMC solving algorithms in POMDP models : Probabilistic theories for decision making in autonomous navigation problems

Sammanfattning

Autonomous navigation problems are a real challenge when working in complex environments where uncertainty and imprecision prevail. In this thesis, we will study a robot that has to find its way through a maze. This situation can easily be modeled using a MDP (Markov Decision Process). A MDP is a reinforcement learning model in which an agent interacts stochastically with its environment. In our problem, the agent is the robot and the environment is the maze. To solve this problem, the robot must find the best actions to perform to reach its goal in the maze. HawAI.tech chose this model because of the possibility of stochastic actions. To manage the uncertainty linked to this stochasticity and solve the MDP, HawAI.tech used an algorithm called MCTS (Monte Carlo Tree Search). This algorithm achieved a success rate of almost 90%. One of the problems we faced was to give the robot access to a noisy version of its real state, rather than its actual state. In real life, sensors, like actuators, are affected by imperfections, so adding noise to the information they provide is consistent. To solve this problem, I improved our MDP representation of the problem into a POMDP (Partially Observable Markov Decision Model). In this situation, the success rate fell to 50%. Another problem was that the MCTS algorithm requires an assumption : the robot must know its exact position at all times. Once this noise had been modeled, and the assumption invalidated, the algorithm was no longer very effective, so we had to change algorithms. I transformed the MCTS algorithm into a POMCP (Partially Observable Monte Carlo Model) algorithm. To do this, I implemented a particle filter. This is a crucial element that enables the algorithm to navigate even when it has only partial and perturbed knowledge of the robot’s position. Thanks to this new feature, I was able to get back to a 93% success rate despite the noise. In addition, a new version of the problem was designed to quantify the algorithm’s handling of uncertainty through benchmarks. These benchmarks were carried out to see whether the robot takes into account the uncertainty of the information it is given for its trajectory planning. The aim was to have a robot capable of planning its trajectory while striking a balance between safety and speed.