Date of Award

Spring 2022

Document Type

Open Access Dissertation


Computer Science and Engineering

First Advisor

Jason O’Kane


In this dissertation, we present a collection of new planning algorithms that enable robots to achieve complex goals, beyond simple point-to-point path planning, using automata-theoretic methods, and we consider the filter minimization (FM) problem and a variant of it, filter partitioning minimization (FPM) problem, which aims to minimize combinatorial filters, used for filtering and automata-theoretic planning in systems with discrete sensor data. We introduce a new variant of bisimulation, compatibility, and using this notion we identify several classes of filters for which FM or FPM is solvable in polynomial time, and propose several integer linear programming (ILP) formulations of FM and FPM. Then, we consider a problem, planning to chronicle, in which a robot is tasked with observing an uncertain time-extended process to produce a ‘chronicle’ of occurrent events that meets a given specification. This problem is useful in applications where we deploy robots to autonomously make structured videos or documentaries from events occurring in an unpredictable environment. Next, we study two variants of temporal logic planning in which the objective is to synthesize a trajectory that satisfies an optimal selection of soft constraints while nevertheless satisfying a hard constraint expressed in linear temporal logic (LTL). We also extend planning to chronicle with the idea of this problem. Then, we consider the problem of planning where to observe the behavior of an agent to ensure that the agent’s execution within the environment fits a pre-disclosed itinerary. This problem arises in a range of contexts including in validating safety claims about robot behavior, applications in security and surveillance, and for both the conception and the (physical) design and logistics of scientific experiments.