Hierarchical Heuristic Search in Stochastic Domains

• Project number: 202-08-13
• Students: Raz Nissim, Ronen Sabag
• Supervisor: Ronen Brafman

This undergraduate project is based on a paper1 written by Ronen Brafman of the Ben-Gurion University's Computer Science department and Nicolas Meuleau of the NASA Ames Research Center. This paper describes a variant to an existing decision making algorithm - AO*(Nilsson 1980), for performing forward heuristic search in hierarchical (stochastic) models.

Many MDPs (Markov Decision Process) exhibit a hierarchical structure where the agent needs to perform various subtasks that are coupled only by a small sub-set of variables containing, notably, shared resources. The new algorithm, HIAO*, aims to take advantage of the hierarchical structure of most MDPs and solve the problems more efficiently.

This algorithm was developed in order to be used on the NASA Mars Rover which currently has sub-optimal plans and spends most of its time idle. The main goal of the project was to show several experimental results that support HIAO* being more efficient than AO*. To do this, we implemented the two algorithms, two heuristic functions (that are needed for the algorithms), several MDPs with two or three-level hierarchy and two improvements to HIAO* that were discussed in the paper. Finally, we performed the experiments and recorded the results.