Modeling Human Planning in Maze Orienteering Problems

To create socially intelligent artificial assistants for humans in complex, naturalistic search environments, we need to develop algorithms that build models of human planning given their past decisions. In this thesis project, I focused on modeling human planning in Maze Orienteering Problems (MOP), an optimization problem with the objective to maximize collected rewards within a time limit in a partially known maze. The project has two main components: developing planning algorithms to find approximate solutions to the MOP and using those algorithms to model human behavior with Bayesian inference. For the planning part, I designed a hierarchical planning framework to solve the MOP as a room-level orienteering problem and a Partially Observable Markov Decision Process (POMDP) inside each room. My evaluation of algorithms shows that a Closest-Room heuristic model for room-level planning performs comparable to Branch-and-Bound exhaustive search while bearing a much smaller computational cost. For the inference part, I implemented an online Bayesian inverse planning framework to fit candidate hierarchical planners to individual human traces. My experiments of human modeling shows that Closest-Room heuristic model also outperforms BnB in fitting humans’ room-level decisions and predicting their next rooms to visit.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Yang, Zhutian

Advisor dc:contributor.advisor

• Shrobe, Howard

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139470

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139470