Hybrid Algorithm to Find Minimum Expected Escape Time From a Maze

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)346-357
Number of pages12
JournalEngineering Letters
Issue number1
Publication statusPublished - 2023


  • and path scenario
  • expected value
  • hybrid algorithm
  • linear alge-bra


Dive into the research topics of 'Hybrid Algorithm to Find Minimum Expected Escape Time From a Maze'. Together they form a unique fingerprint.

Cite this