Robots are becoming more of a part of our daily lives. They have become an extension of some our human capabilities and there is a need to develop control algorithms that contribute to the successful deployment of these machines to navigate, explore and map indoor human environments. These robots and their actions, despite our effort to make them as predictable as possible, show stochastic behaviors, as well as motion and sensing uncertainties. We leverage the use of Constrained Markov Decision Processes (CMDP) to balance multi-cost problems with constraints, under the premise of having multiple possible sources of uncertainties. This dissertation engages in solving some of these problems in the following chapters.

Initially, we highlight some of the theoretical background about Markov Decision Process (MDP) and its extension the CMDP. From this point we deal with the problem of multiple robots visiting multiple targets, while we fix temporal and failure probability constraints. We present our solution to expand the state space following a binary sequence that represents successful observations of each of the targets. All this is classified as the rapid deployment problem, which we define and solve for a team of robots.

Closing the gap between reality and theory, we implement a stochastic model that recreates the motion primitives from a robot. We proceed to use these modeled primitives to create modeled trajectories and extract transition probabilities from them. These transition probabilities characterize some of the robot’s behavior and we use them with our formulation of a CMDP. Then we calculate a navigation policy to traverse some real scenarios.

We create and implement a new spatial model dubbed Oriented Topological Semantic Map (OTSM). This new type of map can be built in run-time, and together with a CMDP, we assign actionable temporal deadlines to the robot executing an exploration task. We open-sourced a ROS framework that can be downloaded and used to reproduce our results and we published the first Reproducible Article or R-article in robotics. Consequently, we implement an OTSM by grouping an Orientation System (OS), an Intersection Detection System (IDS), and a Labeling System (LS), using odometry, accelerometers, a LIDAR, and a residual neural network resNet, to extract the orientation, the topology, and the semantics of an indoor environment.

In the last part of this dissertation we propose a new algorithm to merge together pieces of OTSMs when a group of robots have the task to explore an unknown environment. Then they combine their local maps into a global map. Our solution was inspired from research in cognitive science that focused on object recognition. Applying this theory, we create a two-stage method to compare vertices in different OTSMs and measure their resemblance.