Date of Award

Summer 2020

Document Type

Open Access Dissertation


Computer Science and Engineering

First Advisor

Jason O’Kane


This dissertation is focused on the problem of algorithmic robot design. The process of designing a robot or a team of robots that can reliably accomplish a task in an environment requires several key elements. How the problem is formulated can play a big role in the design process. The ability of the model to correctly reflect the environment, the events, and different pieces of the problem is crucial. Another key element is the ability of the model to show the relationship between different designs of a single system. These two elements can enable design algorithms to navigate through the space of all possible designs, and find a set of solutions. In this dissertation, we introduce procrustean graphs, a model for encoding the robot-environment interactions. We also provide a model for navigating through the space of all possible designs, called label maps. Using these models, we focus on answering the following questions: What degradations to the set of sensors or actuators of a robotic system can be tolerated? How different degradations affect the cost of doing a given task? What sets of resources — that is, sensors and actuators — are minimal for accomplishing a specific given job? And how to find such a set? To this end, our general approach is to sample, using a variety of sampling methods, over the space of all maps for a given problem, and use different techniques for answering these questions. We use decision tree classifiers to determine the crucial sensors and actuators required for a robotic system to accomplish its job. We present an algorithm based on space bisection to find the boundary between the feasible and infeasible subspaces of possible designs. We present an algorithm to measure the cost of doing a given task, and another algorithm to find the relationship between different degradation of a robotic system and the cost of doing the task. In all these solutions, we use a variety of techniques to scale up each approach to enable it to solve real world problems. Our experiments show the efficiency of the presented approach.