Hybrid Algorithm to Find Minimum Expected Escape Time From a Maze

Expected value is one of the important factors used in scenario analysis and decision makings. The most commonly known method in finding expected value of a probability problem is using deterministic approach to formulate and solve a system of linear equations that represent the given problem. This method, nonetheless, requires unrealistic conditions for it to be executable which are knowing all the scenarios that might happen and the probability for each scenario to happen. In real life situations, most problems do not have a definite scenarios provided with each of their probabilities. This is a major loophole in deterministic approach for finding an expected value of certain problems. One specific probability problem that has this issue is to find the minimum expected time needed to escape from a two-dimensional maze without any information given for the escape path and the movement probabilities. In this paper, we propose a novel solution for the aforementioned problem using hybrid algorithm which is a combination of deterministic and heuristic approach. In our hybrid algorithm, the heuristic method is for optimizing the assembly of possible path scenarios, while the deterministic method is for counting and finding the minimum expected time for each path scenario. Based on the case study testing result, the solution using this hybrid algorithm requires an average time of only 2.4 seconds which is seven times faster than the required time limit, and an average memory of 5.31MB which is only using 0.3% resources from the required memory limit.