Ryan K. Williams

Ryan Williams

Computational modeling is a critical tool for understanding consciousness, but is it enough on its own? This paper discusses the necessity for an ontological basis of consciousness, and introduces a formal framework for grounding computational descriptions into an ontological substrate. Utilizing this technique, a method is demonstrated for estimating the difference in qualitative experience between two systems. This framework has wide applicability to computational theories of consciousness.

Ryan Williams

This paper aims to show that a simple framework, utilizing basic formalisms from set theory and category theory, can clarify and inform our theories of the relation between mind and matter.

Ashrarul H. Sifat, Burhanuddin Bharmal, Haibo Zeng et al.

The potential impact of autonomous robots on everyday life is evident in emerging applications such as precision agriculture, search and rescue, and infrastructure inspection. However, such applications necessitate operation in unknown and unstructured environments with a broad and sophisticated set of objectives, all under strict computation and power limitations. We therefore argue that the computational kernels enabling robotic autonomy must be scheduled and optimized to guarantee timely and correct behavior, while allowing for reconfiguration of scheduling parameters at run time. In this paper, we consider a necessary first step towards this goal of computational awareness in autonomous robots: an empirical study of a base set of computational kernels from the resource management perspective. Specifically, we conduct a data-driven study of the timing, power, and memory performance of kernels for localization and mapping, path planning, task allocation, depth estimation, and optical flow, across three embedded computing platforms. We profile and analyze these kernels to provide insight into scheduling and dynamic resource management for computation-aware autonomous robots. Notably, our results show that there is a correlation of kernel performance with a robot's operational environment, justifying the notion of computation-aware robots and why our work is a crucial step towards this goal.

Pratik Mukherjee, Matteo Santilli, Andrea Gasparri et al.

In this paper, we consider two coupled problems for distributed multi-robot systems (MRSs) coordinating with limited field of view (FOV) sensors: adaptive tuning of interaction gains and rejection of sensor attacks. First, a typical shortcoming of distributed control frameworks (e.g., potential fields) is that the overall system behavior is highly sensitive to the gain assigned to relative interactions. Second, MRSs with limited FOV sensors can be more susceptible to sensor attacks aimed at their FOVs, and therefore must be resilient to such attacks. Based on these shortcomings, we propose a comprehensive solution that combines efforts in adaptive gain tuning and attack resilience to the problem of topology control for MRSs with limited FOVs. Specifically, we first derive an adaptive gain tuning scheme based on satisfying nominal pairwise interactions, which yields a dynamic balancing of interaction strengths in a robot's neighborhood. We then model additive sensor and actuator attacks (or faults) and derive H infinity control protocols by employing a static output-feedback technique, guaranteeing bounded L2 gains of the error induced by the attack (fault) signals. Finally, simulation results using ROS Gazebo are provided to support our theoretical findings.

Jun Liu, Murtaza Rangwala, Kulbir Singh Ahluwalia et al.

Monitoring the health and vigor of grasslands is vital for informing management decisions to optimize rotational grazing in agriculture applications. To take advantage of forage resources and improve land productivity, we require knowledge of pastureland growth patterns that is simply unavailable at state of the art. In this paper, we propose to deploy a team of robots to monitor the evolution of an unknown pastureland environment to fulfill the above goal. To monitor such an environment, which usually evolves slowly, we need to design a strategy for rapid assessment of the environment over large areas at a low cost. Thus, we propose an integrated pipeline comprising of data synthesis, deep neural network training and prediction along with a multi-robot deployment algorithm that monitors pasturelands intermittently. Specifically, using expert-informed agricultural data coupled with novel data synthesis in ROS Gazebo, we first propose a new neural network architecture to learn the spatiotemporal dynamics of the environment. Such predictions help us to understand pastureland growth patterns on large scales and make appropriate monitoring decisions for the future. Based on our predictions, we then design an intermittent multi-robot deployment policy for low-cost monitoring. Finally, we compare the proposed pipeline with other methods, from data synthesis to prediction and planning, to corroborate our pipeline's performance.

Jun Liu, Ryan K. Williams

In this paper, we demonstrate a formulation for optimizing coupled submodular maximization problems with provable sub-optimality bounds. In robotics applications, it is quite common that optimization problems are coupled with one another and therefore cannot be solved independently. Specifically, we consider two problems coupled if the outcome of the first problem affects the solution of a second problem that operates over a longer time scale. For example, in our motivating problem of environmental monitoring, we posit that multi-robot task allocation will potentially impact environmental dynamics and thus influence the quality of future monitoring, here modeled as a multi-robot intermittent deployment problem. The general theoretical approach for solving this type of coupled problem is demonstrated through this motivating example. Specifically, we propose a method for solving coupled problems modeled by submodular set functions with matroid constraints. A greedy algorithm for solving this class of problem is presented, along with sub-optimality guarantees. Finally, practical optimality ratios are shown through Monte Carlo simulations to demonstrate that the proposed algorithm can generate near-optimal solutions with high efficiency.

Jun Liu, Ryan K. Williams

In this paper, we formulate and solve the intermittent deployment problem, which yields strategies that couple \emph{when} heterogeneous robots should sense an environmental process, with where a deployed team should sense in the environment. As a motivation, suppose that a spatiotemporal process is slowly evolving and must be monitored by a multi-robot team, e.g., unmanned aerial vehicles monitoring pasturelands in a precision agriculture context. In such a case, an intermittent deployment strategy is necessary as persistent deployment or monitoring is not cost-efficient for a slowly evolving process. At the same time, the problem of where to sense once deployed must be solved as process observations yield useful feedback for determining effective future deployment and monitoring decisions. In this context, we model the environmental process to be monitored as a spatiotemporal Gaussian process with mutual information as a criterion to measure our understanding of the environment. To make the sensing resource-efficient, we demonstrate how to use matroid constraints to impose a diverse set of homogeneous and heterogeneous constraints. In addition, to reflect the cost-sensitive nature of real-world applications, we apply budgets on the cost of deployed heterogeneous robot teams. To solve the resulting problem, we exploit the theories of submodular optimization and matroids and present a greedy algorithm with bounds on sub-optimality. Finally, Monte Carlo simulations demonstrate the correctness of the proposed method.

Jun Liu, Lifeng Zhou, Pratap Tokekar et al.

In this letter, we consider a distributed submodular maximization problem for multi-robot systems when attacked by adversaries. One of the major challenges for multi-robot systems is to increase resilience against failures or attacks. This is particularly important for distributed systems under attack as there is no central point of command that can detect, mitigate, and recover from attacks. Instead, a distributed multi-robot system must coordinate effectively to overcome adversarial attacks. In this work, our distributed submodular action selection problem models a broad set of scenarios where each robot in a multi-robot system has multiple action selections that may fulfill a global objective, such as exploration or target tracking. To increase resilience in this context, we propose a fully distributed algorithm to guide each robot's action selection when the system is attacked. The proposed algorithm guarantees performance in a worst-case scenario where up to a portion of the robots malfunction due to attacks. Importantly, the proposed algorithm is also consistent, as it is shown to converge to the same solution as a centralized method. Finally, a distributed resilient multi-robot exploration problem is presented to confirm the performance of the proposed algorithm.

Barnabas Gavin Cangan, Larkin Heintzman, Amanda Hashimoto et al.

In this work, our goal is to extend the existing search and rescue paradigm by allowing teams of autonomous unmanned aerial vehicles (UAVs) to collaborate effectively with human searchers on the ground. We derive a framework that includes a simulated lost person behavior model, as well as a human searcher behavior model that is informed by data collected from past search tasks. These models are used together to create a probabilistic heatmap of the lost person's position and anticipated searcher trajectories. We then use Gaussian processes with a Gibbs' kernel to accurately model a limited field-of-view (FOV) sensor, e.g., thermal cameras, from which we derive a risk metric that drives UAV path optimization. Our framework finally computes a set of search paths for a team of UAVs to autonomously complement human searchers' efforts.

Pratik Mukherjee, Matteo Santilli, Andrea Gasparri et al.

In this paper, we address the problem of stable coordinated motion in multi-robot systems with limited fields of view (FOVs). These problems arise naturally for multi-robot systems that interact based on sensing, such as our case study of multiple unmanned aerial vehicles (UAVs) each equipped with several cameras that are used for detecting neighboring UAVs. In this context, our contributions are: i) first, we derive a framework for studying stable motion and distributed topology control for multi-robot systems with limited FOVs; and ii) Then, we provide experimental results in indoor and challenging outdoor environments (e.g., with wind speeds up to 10 mph) with a team of UAVs to demonstrate the performance of the proposed control framework using a portable multi-robot experimental set-up.

Yoonchang Sung, Ashish Kumar Budhiraja, Ryan K. Williams et al.

We study a multi-robot assignment problem for multi-target tracking. The proposed problem can be viewed as the mixed packing and covering problem. To deal with a limitation on both sensing and communication ranges, a distributed approach is taken into consideration. A local algorithm gives theoretical bounds on both the running time and approximation ratio to an optimal solution. We employ a local algorithm of max-min linear programs to solve the proposed task. Simulation result shows that a local algorithm is an effective solution to the multi-robot task allocation.

Lane A. Hemaspaandra, Ryan Williams

Heuristic approaches often do so well that they seem to pretty much always give the right answer. How close can heuristic algorithms get to always giving the right answer, without inducing seismic complexity-theoretic consequences? This article first discusses how a series of results by Berman, Buhrman, Hartmanis, Homer, Longpré, Ogiwara, Schöening, and Watanabe, from the early 1970s through the early 1990s, explicitly or implicitly limited how well heuristic algorithms can do on NP-hard problems. In particular, many desirable levels of heuristic success cannot be obtained unless severe, highly unlikely complexity class collapses occur. Second, we survey work initiated by Goldreich and Wigderson, who showed how under plausible assumptions deterministic heuristics for randomized computation can achieve a very high frequency of correctness. Finally, we consider formal ways in which theory can help explain the effectiveness of heuristics that solve NP-hard problems in practice.