Multicriteria Pathfinding in Uncertain Simulated Environments
Andrew R. Buck
Ph.D. Dissertation, Dept. Elect. Eng. Comp. Sci., Univ. Missouri, Columbia, MO, USA, 2018
Ph.D. Dissertation, Pathfinding, MCDM, Mental Map
Abstract
Multicriteria decision-making problems arise in all aspects of daily life and form the basis upon which high-level models of thought and behavior are built. These problems present various alternatives to a decision-maker, who must evaluate the trade-offs between each one and choose a course of action. In a sequential decision-making problem, each choice can influence which alternatives are available for subsequent actions, requiring the decision-maker to plan ahead in order to satisfy a set of objectives. These problems become more difficult, but more realistic, when information is restricted, either through partial observability or by approximate representations.
Pathfinding in partially observable environments is one significant context in which a decision-making agent must develop a plan of action that satisfies multiple criteria. In general, the partially observable multiobjective pathfinding problem requires an agent to navigate to certain goal locations in an environment with various attributes that may be partially hidden, while minimizing a set of objective functions. To solve these types of problems, we create agent models based on the concept of a mental map that represents the agent's most recent spatial knowledge of the environment, using fuzzy numbers to represent uncertainty. We develop a simulation framework that facilitates the creation and deployment of a wide variety of environment types, problem definitions, and agent models. This computational mental map (CMM) framework is shown to be suitable for studying various types of sequential multicriteria decision-making problems, such as the shortest path problem, the traveling salesman problem, and the traveling purchaser problem in multiobjective and partially observable configurations.
Media
Cellular automata environment generation using region dilation.
Cellular automata environment generation using random expansion.
A greedy algorithm solving a CMM problem with no region clustering.
A greedy algorithm solving a CMM problem using region clustering with no local region memory.
A greedy algorithm solving a CMM problem using region clustering with local region memory.
A greedy algorithm solving a CMM problem using region clustering only for unobserved regions.
A greedy algorithm for solving the partially observable travelling salesman problem (PO-TSP).
A myopic Monte Carlo (MMC) algorithm for solving the partially observable travelling salesman problem (PO-TSP).
Ant Colony Optimization (ACO) for solving the TSP in the CMM framework.
Files
[dissertation]
[slides]