| dc.description.abstract | Roboticists design robots by relying heavily on empirical knowledge and prior experience. That design process is seldom done in an automated fashion. This dissertation aims to automate robot design for robots for estimation and planning tasks. The work shows how to make decisions about robot hardware choices while jointly solving for a plan or estimator. To do so, this dissertation reasons about the information required by the task and the information that can be collected by a robot with a particular design. The robot should be able to provide sufficient information to accomplish a task. But such information can be both valuable and sensitive, and can be potentially leaked from the robot. Motivated by applications where privacy is important, this dissertation studies automated robot design for planning and estimation tasks, subject to additional constraints on the information that can be disclosed by or learned from the robot. It investigates the design of robot sensors, the information disclosure policy that determines how information is disclosed from the robot, and prior knowledge in privacy-preserving tracking and planning tasks. It also develops exact algorithms to construct estimators, which have minimum state complexity and achieve specified functionalities in the estimation tasks.
We first characterize the strategy space of one-dimensional privacy-preserving tracking problems, where a robot must track a target with its accuracy above a tracking bound and below a privacy bound. We present impossibility results for some tracking and privacy bounds, and show that the feasibility of the task is sensitive to the robot's initial belief. By characterizing sensor power as the number of its pre-images, we prove that the amount of solvable privacy-preserving problems is bounded, converging asymptotically with increasing sensing power.
Secondly, we examine privacy-preserving planning problems, where the robot should not only solve the planning problem but also reason about the disclosed information of the plan execution to a third party we call an observer---these are active variants of the passive problem we first consider. In this problem, we introduce the notion of information disclosure policy to create a knowledge gap between the observations perceived by the robot and the information received by the observer during plan execution. In addition, we also examine different assumptions about the observer's prior knowledge of the robot's plan, and present a family of algorithms to search for a plan and an information disclosure policy. Among the problems that are solved, the most challenging one is to search for a plan and information disclosure policy, while assuming the same plan is disclosed as prior knowledge to the observer. In this problem, before the plan is found, there is no explicit representation of the observer's prior knowledge, which makes the plan search problem challenging to formulate.
Next, we consider robot sensors abstractly. Due to the sensor noise, there is a gap between what the robot sees and the real event happening in the world. We model such a sensing gap with a formal structure that generalizes information disclosure policy, and this structure serves as an abstraction of the sensor. We further model sensor fabrication constraints (such as sensing fidelity) as properties of the abstraction, and propose search algorithms to enumerate all sensors that suffice for solving a planning problem.
Finally, we study the minimization problems of the combinatorial filters, which are the discrete estimators used by the observer in the privacy-preserving planning problems. We generalize the existing notion of combinatorial filters and examine the hardness of both deterministic and non-deterministic filter minimization problems. We show that multiple concepts previously believed to be true about combinatorial filters (and actually conjectured, claimed, or assumed to be) are in fact false. We then present the first known complete filter minimization algorithm, and further propose an algorithm that is efficient in practice.
To summarize, this dissertation includes impossibility results for sensor design in privacy-preserving tracking tasks, and algorithms for finding plans, sensor-plan pairs, and disclosure-plan pairs to enable automated design in privacy-preserving planning tasks. It also contributes counter-examples, constructions, hardness results, and algorithms to minimize the state complexity of combinatorial filters. | en |
