UC Merced

Robotic technologies have advanced significantly that improved capabilities of robots. Such robots operate in complicated environments

and are exposed to multiple resources of uncertainties. The uncertainties causes robots actions to be non-deterministic.

Robot planning in non-deterministic environments is a challenging problem that has been extensively discussed in the literature.

In this dissertation, we tackle this class of problems and are more particularly

interested in finding an optimal solution while the robot faces several constraints. To do so, we leverage Constrained Markov Decision Processes (CMDPs)

which are extensions to Markov Decision Processes (MDPs) by supporting multiple costs and constraints. Despite all the capabilities of CMDPs,

they are not very popular in robot planning. One of our goals in this work is to show that CMDPs can also be used in robot planning.

In the first part of this dissertation, we focus on optimizing CMDPs to solve large problems in a timely manner. Therefore, we

propose a hierarchical approach that significantly reduces the computational time of solving a CMDP instance while preserving the

existence of a valid solution. In other words, the Hierarchical CMDP (HCMDP) guarantees to find a valid solution for a specific problem

if the non-hierarchical CMDP is able to find one. Although, the experimental evaluation shows that the HCMDP and the non-hierarchical CMDP

generate comparable results, we do not provide any guarantees in terms of optimality.

In the second part, we aim for more complicated constraints represented as tasks. Tasks are usually specified by Linear Temporal Logic (LTL) properties

and determine a desired temporal sequence of states to be visited by the robot. For instance, an autonomous forklift may be tasked to go to a pick-up station,

load an object, drive toward a delivery point and drop it off. As seen the order of states is critical. Thus, we propose a planner

that finds a plan to satisfy multiple tasks with given probabilities while having various constraints on its cost functions.

The proposed solver utilizes the theory of LTL properties to define tasks, and the theory of CMDPs to find an optimal solution.

We also present a special form of product operation between LTL properties and CMDPs that is repeatable. This repeatability lets us

apply the product operation several times to take all of the tasks into account. The proposed approach is extensively tested in

Matlab, robot simulation and on a real robot.

This solver runs the product operation many times which results in increasing number of states. Therefore, it is crucial to reduce the number of

states in order to have a faster solver. In part three of this thesis, we aim for optimizing the solver in part two. We propose two improvements.

The first improvement considers the order of product operations. Although the product operation is commutative and the order of operations

does not influence the final result, it affects the computational time. Thus, we present an algorithm to find the best order of operations.

The second improvement runs a pruning algorithm to reduce the number of states by removing the states that play little or no role in the final product.

As opposing to the first improvement, it may change the final solution. However, we analyze different cases that may appear and show the effects.