Browsing by Subject "Robotics"

Reasoning about 3D objects is one of the most critical perception problems robots face; outside of navigation, most interactions between a robot and its environment are object-centric. Object-centric robot perception has long relied on maintaining an explicit database of 3D object models with the assumption that encountered objects will be exact copies of entries in the database; however, as robots move into unstructured environments such as human homes, the variation of encountered objects increases and maintaining an explicit object database becomes infeasible. This thesis introduces a general-purpose 3D object representation that allows the joint estimation of a previously unencountered object's class, pose, and 3D shape---crucial foundational tasks for general robot perception.

We present the first method capable of performing all three of these tasks simultaneously, Bayesian Eigenobjects (BEOs), and show that it outperforms competing approaches which estimate only object shape and class given a known object pose. BEOs use an approximate Bayesian version of Principal Component Analysis to learn an explicit low-dimensional subspace containing the 3D shapes of objects of interest, which allows for efficient shape inference at high object resolutions. We then extend BEOs to produce Hybrid Bayesian Eigenobjects (HBEOs), a fusion of linear subspace methods with modern convolutional network approaches, enabling realtime inference from a single depth image. Because HBEOs use a Convolutional Network to project partially observed objects onto the learned subspace, they allow the object to be larger and more expressive without impacting the inductive power of the model. Experimentally, we show that HBEOs offer significantly improved performance on all tasks compared to their BEO predecessors. Finally, we leverage the explicit 3D shape estimate produced by BEOs to further extend the state-of-the-art in category level pose estimation by fusing probabilistic pose predictions with a silhouette-based reconstruction prior. We also illustrate the advantages of combining both probabilistic pose estimation and shape verification, via an ablation study, and show that both portions of the system contribute to its performance. Taken together, these methods comprise a significant step towards creating a general-purpose 3D perceptual foundation for robotics systems, upon which problem-specific systems may be built.

In surgical robotics, fully-automated tumor removal is an important topic and it includes three main tasks: tissue classification for cancer diagnosis, pathological mapping for tumor localization and tissue resection by using a laser scalpel. Generating a three-dimensional (3D) pathological tissue model with fully non-contact sensors can provide invaluable information to assist surgeons in decision-making and enable the use of surgical robots for efficient tissue manipulation. To collect the comprehensive information of a biological tissue target, robotic laser systems with complementary sensors (e.g., Optical coherence tomography (OCT) sensor, and stereovision) can play important roles in providing non-contact laser scalpels (i.e., cutting laser scalpel) for tissue removal, applying photonics-based sensors for pathological tissue classification (i.e., laser-based endogenous fluorescence), and aligning multi-sensing information to generate a 3D pathological map. However, there are three main challenges with integrating multiple laser-based sensors into the robotic laser system, which includes: 1) Modelling the laser beam transmission in 3D free-space to achieve accurate laser-tissue manipulation under geometric constraints, 2) Studying the complex physics of laser-tissue interaction for tissue differentiation and 3D shape modelling to ensure safe tissue removal, and 3) Integrating information from multiple sensing devices under sensor noise and uncertainties from system calibration.

Targeting these three research problems separately, a computational framework is proposed to provide kinematics and calibration algorithms to control and direct the 3D laser beam through a system with multiple rotary mirrors (to transmit laser beam in free-space) and laser-based sensor inputs. This framework can serve as a base platform for optics-based robotic system designs and solving the motion planning problems related to laser-based robot systems. Simulation experiments have verified the feasibility of the proposed framework and actual experiments have been conducted with an existing robotic laser system on phantom and ex-vivo biological tissues.

To study the complex physics of laser-tissue interaction, a 3D data-driven method is developed to model the geometric relation between the laser energy distribution, laser incident angles, and the tissue deformation resulting from photoablation. The results of the phantom studies have demonstrated the feasibility of applying the trained model for laser crater shape predictions during the surgical planning.

Finally, a research platform, referred as ``TumorMapping", is developed to collect multimodal sensing information from complementary sensors to build a 3D pathological map of a mice tumor surface. This robot system includes a sensor module attached to a 6-DOF robot arm end-effector, based on the laser-induced fluorescence spectroscopy for tissue classification and a fiber couple cutting laser for tissue resection. A benchtop sensor platform is built with an OCT sensor and a stereovision system with two lens camera to collect the tissue information with a non-contact pattern. The robot-sensor and the complementary sensor sub-systems are integrated in a unified platform for the 3D pathological map reconstruction.

In summary, the research contributions include important advancements in laser-based sensor fusion for surgical decision-making which is enabling new capabilities for the use of 3D pathological mapping combined with intelligent robot planning and control algorithms for robotic surgery.

This thesis develops a novel solution method for the problem of collision-free, optimal control of a robotic vehicle in an obstacle populated environment. The technique presented combines the well established approximate cell decomposition methodology with disjunctive programming in order to address both geometric and kinematic trajectory concerns. In this work, an algorithm for determining the shortest distance, collision-free path of a robot with unicycle kinematics is developed. In addition, the research defines a technique to discretize nonholonomic vehicle kinematics into a set of mixed integer linear constraints. Results obtained using the Tomlab/CPLEX mixed integer quadratic programming software exhibit that the method developed provides a powerful initial step in reconciling geometric path planning methods with optimal control techniques.

Across multiple industries (e.g., railroads, airlines, on-demand air taxi services), there are growing investments in future automated transportation systems. Even with these investments, there are still significant human-systems engineering challenges that require deeper investigation and planning. Specifically, fleets that include new levels of automation may require new concepts of how to design and staff network operations centers. Network operations centers have existed for over a century in the railroad and airline industries, where dispatchers have played a central role in safely and efficiently managing networks of railroads and flights. With operators in such safety-critical and time-sensitive positions, workload is the key indicator of their performance in terms of accuracy and efficiency. Yet, there are few tools available for decision-makers in these industries to explore how increasing levels of automation in fleets and operations centers may ultimately affect dispatcher workload.

Thus, this thesis presents a model of dispatcher workload. While automation may be the most pressing change in transportation industries, 10 variables related to configurations of the fleet and the operations center and how those variables interact to influence dispatcher workload were defined. These ten variables come from fleet conditions, strategic design factors, tactical staffing factors, and operational factors. A discrete event simulation was developed to computationally model dispatcher workload with over 10^18 possible configurations of these variables. Additionally, using time-based metrics and integrating results from a prior human reliability assessment, the simulation predicts human error on tasks.

A multi-level validation strategy was developed to build internal, external, and general confidence in using the dispatcher workload model across different domains with data from freight railroad, commuter railroad, and airline operations. In the process of developing and validating the workload model, several other research contributions were made to the field. Eighty-five probability density functions of dispatcher task inter-arrival and service time distributions were generated in the three domains. A data collection tool, Dispatcher’s Rough Assessment of Workload-Over Usual Times (DRAW-OUT), was designed to gather empirical dispatcher-generated estimates of utilization, the proxy for workload, throughout their shifts.

Using the model, experiments were conducted to analyze the sensitivity of dispatcher workload and performance to changes in different parameters. The size of the fleet a dispatcher managed was found to be the most significant factor out of all the other internal parameters. On the other hand, shift schedule, environmental conditions, and operator strategy were the parameters found to have the smallest influence on dispatcher performance. The model was also used to investigate future scenarios that managers could not previously explore due to limitations of time and resources. Results show that the general model is applicable for use in simulating dispatcher workload in both freight and commuter railroad operations as well as airline operations, including short- and long-haul flights, in present-day and future cases.

General confidence was built in the workload model and the Simulator of Humans & Automation in Dispatch Operations (SHADO) was developed as an online platform to provide open access to the underlying discrete event simulation. SHADO is a novel tool that allows stakeholders, including operational managers, to rapidly prototype dispatch operations and investigate human performance in any transportation system. With several theoretical and practical contributions, this work establishes the foundation for future research in the growing field of advanced transportation network operations.

Robotics has the potential to dramatically change society over the next decade. Technology has matured such that modern robots can execute complex motions with sub-millimeter precision. Advances in sensing technology have driven down the price of depth cameras and increased their performance. However, the planning algorithms used in currently-deployed systems are too slow to react to changing environments; this has restricted the use of high degree-of-freedom (DOF) robots to tightly-controlled environments where planning in real time is not necessary.

Our work focuses on overcoming this challenge through careful hardware/software co-design. We leverage aggressive precomputation and parallelism to design accelerators for several components of the motion planning problem. We present architectures for accelerating collision detection as well as path search. We show how we can maintain flexibility even with custom hardware, and describe microarchitectures that we have implemented at the register-transfer level. We also show how to generate effective planning roadmaps for use with our designs.

Our accelerators bring the total planning latency to less than 3 microseconds, several orders of magnitude faster than the state of the art. This capability makes it possible to deploy systems that plan under uncertainty, use complex decision making algorithms, or plan for multiple robots in a workspace. We hope this technology will push robotics into domains and applications that were previously infeasible.

Laser scalpels are utilized across a variety of invasive and non-invasive surgical procedures due to their precision and non-contact nature. Meanwhile, robotic and robotic-assisted surgeries are becoming more prevalent with the promise of improving surgical outcomes through increased precision, reduced operating times, and minimally invasive procedures. This dissertation presents methods and devices developed to enable assistive robotic laser surgery, with the goal of realizing the surgical benefits of both and ultimately improving surgical outcomes for patients.

The device is first used to demonstrate targeted soft tissue resection in porcine brain in an open-loop fashion. This device, coined the "TumorCNC" combines 3D scanning capabilities with a steerable surgical laser. Results show high variance around target cut depths which motivats the need for a closed-loop feedback and control as well as characterization of laser-tissue interactions for predictive modeling.

To begin to address the technical difficulties of closed-loop ablation, a model-based approach is taken. A soft tissue ablation simulator is developed and used in conjunction with an optimization routine to select parameters which maximize the total resection of target tissue while minimizing the damage to surrounding tissue. The optimization is performed using genetic algorithms. The simulator predicts the ablative properties of tissue from an interrogation cut for tuning and simulates the removal of a tumorous tissue embedded on the surface of healthy tissue using a laser scalpel. This demonstrates the ability to control depth and smoothness of cut using genetic algorithms to optimize the ablation parameters and cutting path. The laser power level, cutting rate and spacing between cuts are optimized over multiple surface cuts to achieve the desired resection volumes.

Noting that the modeling approached developed is applicable to other laser treatments requiring uniformity of laser energy deposition, a study of superficial region ablation is performed for applications in dermatology. The TumorCNC is now outfitted with an RGB-D camera. To accurately ablate targets chosen from the color image, a 3D extrinsic calibration method between the RGB-D camera frame and the laser coordinate system is implemented. The accuracy of the calibration method is tested on phantoms with planar and cylindrical surfaces. Positive error and negative error, as defined as undershooting and overshooting over the target area, are reported for each test. For 60 total test cases, the root-mean-square of the positive and negative error in both planar and cylindrical phantoms is less than 1.0mm, with a maximum absolute error less than 2.0mm. This work demonstrates the feasibility of automated laser therapy with surgeon oversight via our sensor system.

As a demonstration of the culmination of these techniques, a closed-loop, adaptive online estimation of ablative properties for soft tissue laser resection of tumors is demonstrated. First, a laser photoablation feature is created in an agarose based tissue phantom using a robotic laser photoablation device equipped with a carbon dioxide laser. Second, the device measures the surface profile of the ablated feature for analysis. Genetic algorithms in conjunction with the photoablation simulator based on the steady-state photoablation model are used to estimate the photoablation enthalpy, density, and ablative radiant threshold of the tissue phantom. The parameters and model are validated through comparison of predicted and measured surface ablations at varying depths. This approach proved effective for predicting the resulting surface profiles for small cut depths (<= 2mm) and generating laser cut paths to reach a desired depth of cut for a large surface area. This work is enabling of closed-loop resection of tissue in robotic laser surgery.

Being able to adapt to different tasks is a staple of learning, as agents aim to generalize across different situations. Specifically, it is important for agents to adapt to the policies of other agents around them. In swarm settings, multi-agent sports settings, or other team-based environments, agents learning from one another can save time and reduce errors in performance. As a result, traditional transfer reinforcement learning proposes ways to decrease the time it takes for an agent to learn from an expert agent. However, the problem of transferring knowledge across agents that operate in different action spaces and are therefore heterogeneous poses new challenges. Mainly, it is difficult to translate between heterogeneous agents whose action spaces are not guaranteed to intersect.

We propose a transfer reinforcement learning algorithm between heterogeneous agents based on a subgoal trajectory mapping algorithm. We learn a mapping between expert and learner trajectories that are expressed through subgoals. We do so by training a recurrent neural network on trajectories in a training set. Then, given a new task, we input the expert's trajectory of subgoals into the trained model to predict the optimal trajectory of subgoals for the learner agent. We show that the learner agent is able to learn an optimal policy faster with this predicted trajectory of subgoals.

It is equally important for agents to adapt to the intentions of agents around them. To this end, we propose an inverse reinforcement learning algorithm to estimate the reward function of an agent as it updates its policy over time. Previous work in this field assume the reward function is approximated by a set of linear feature functions. Choosing an expressive enough set of feature functions can be challenging, and failure to do so can skew the learned reward function. Instead, we propose an algorithm to estimate the policy parameters of the agent as it learns, bundling adjacent trajectories together in a new form of behavior cloning we call bundle behavior cloning. Our complexity analysis shows that using bundle behavior cloning, we can attain a tighter bound on the difference between the distribution of the cloned policy and that of the true policy than the same bound achieved in standard behavior cloning. We show experiments where our method achieves the same overall reward using the estimated reward function as that learnt from the initial trajectories, as well as testing the feasibility of bundle behavior cloning with different neural network structures and empirically testing the effect of the bundle choice on performance.

Finally, due to the need for agents to adapt to environments that are prone to change due to damage or detection, we propose the design of a robotic sensing agent to detect damage. In such dangerous environments, it may be unsafe for human operators to manually take measurements. Current literature in structural health monitoring proposes sequential sensing algorithms to optimize the number of locations measurements need to be taken at before locating sources of damage. As a result, the robotic sensing agent we designed is mobile, semi-autonomous, and precise in measuring a location on the model structure we built. We detail the components of our robotic sensing agent, as well as show measurement data taken from our agent at two locations on the structure displaying little to no noise in the measurement.

"Anthropomorphic Attachments" undertakes an examination of the human as a highly nebulous, fluid, multiple, and often contradictory concept, one that cannot be approached directly or in isolation, but only in its constitutive relationality with the world. Rather than trying to find a way outside of the dualism between human and not-human, I take up the concept of anthropomorphization as a way to hypersaturate the question of the human. Within this hypersaturated field of inquiry, I focus on the specific anthropomorphic relationalities between human and humanoid technology. Focusing primarily on contemporary U.S. technologies and cultural forms, my dissertation looks at artificial intelligence and robotics in conversation with their cultural imaginaries in contemporary literature, science fiction, film, performance art, and video games, and in conversation with contemporary philosophies of the human, the posthuman, and technology. In reading these discourses as shaping, informing, and amplifying each other and the multiple conceptions of the human they articulate, "Anthropomorphic Attachments" attends to these multiple humans and the multiple morphologies by which anthropomorphic relationalities imagine and inscribe both humanoid technologies and the human itself.

With the unprecedented growth of the E-Commerce market, robotic warehouse automation has attracted much interest and capital investment. Compared to a conventional labor-intensive approach, an automated robot warehouse brings potential benefits such as increased uptime, higher total throughput, and lower accident rates. To date, warehouse automation has mostly developed in inventory mobilization and object picking.

Recently, one area that has attracted a lot of research attention is automated packaging or packing, a process during which robots stow objects into small confined spaces, such as shipping boxes. Automatic item packing is complementary to item picking in warehouse settings. Packing items densely improves the storage capacity, decreases the delivery cost, and saves packing materials. However, it is a demanding manipulation task that has not been thoroughly explored by the research community.

This dissertation focuses on packing objects of arbitrary shapes and weights into a single shipping box with a robot manipulator. I seek to advance the state-of-the-art in robot packing with regards to optimizing container size for a set of objects, planning object placements for stability and feasibility, and increasing robustness of packing execution with a robot manipulator.

The three main innovations presented in this dissertation are:

1. The implementation of a constrained packing planner that outputs stable and collision-free placements of objects when packed with a robot manipulator. Experimental evaluation of the method is conducted with a realistic physical simulator on a dataset of scanned real-world items, demonstrating stable and high-quality packing plans compared with other 3D packing methods.

2. The proposal and implementation of a framework for evaluating the ability to pack a set of known items presented in an unknown order of arrival within a given container size. This allows packing algorithms to work in more realistic warehouse scenarios, as well as provides a means of optimizing container size to ensure successful packing under unknown item arrival order conditions.

3. The systematic evaluation of the proposed planner under real-world uncertainties such as vision, grasping, and modeling errors. To conduct this evaluation, I built a hardware and software packing testbed that is representative of the current state-of-the-art in sensing, perception, and planing. An evaluation of the testbed is then performed to study the error sources and to model their magnitude. Subsequently, robustness measures are proposed to improve the packing success rate under such errors.

Overall, empirical results demonstrate that a success rate of up to 98\% can be achieved by a physical robot despite real-world uncertainties, demonstrating that these contributions have the potential to realize robust, dense automatic object packing.

Recently multi-agent navigation robots have been gaining increasing popularity indiverse applications such as agriculture, package delivery, exploration, search and rescue due to their maneuverability and collaborativity. The control algorithm is the nucleus of such intelligent and autonomous robots performing tasks. In real-world applications, the robots are subjected to nonlinear dynamics, external disturbances, actuator saturation/dynamics, and modeling, estimation, and measurement errors. Furthermore, teams of robots are needed to perform collaboratively while ensuring inter-robot and robot-obstacle collision avoidance.

To address these needs, a novel control paradigm has been developed for multiagent navigation robots that possesses safety, robustness, resilience, scalability, and computation efficiency. The control rule is fully defined by the current active subset of a superset of inequality constraints, which contrasts methods of minimizing a weighted cost function subject to stability constraints. The advantages of this method are that

• the constraints (equality, inequality, holonomic, nonholonomic, scleronomic, rheonomic, etc.) can be handled without trying to \look ahead" to a finite time horizon;• the nonlinear control actions are specified by instantly solving a linear matrix equation; • it does not involve a cost function; • it does not involve any dynamics linearization; • the control parameters are physically interpretable; • actuator saturation and actuator dynamics are readily incorporated; and • it is applicable to fully nonlinear, time-varying, and/or arbitrary-order dynamical systems; and • it can simultaneously control the position and orientation of mechanical systems in one unified step.

These features are achieved through a novel generalization of Gauss’s Principleof Least Constraint (GPLC). GPLC was originally conceived to incorporate hard equality constraints into second-order dynamical systems. The contribution of this dissertation is to define the control actions from the Lagrange multipliers associated with inequality constraints (e.g., collision avoidance constraints) and to accommodate dynamical systems of any order. Thus, the constrained equations of motion are expressed as a Karush-Kuhn-Tucker (KKT) system (a linear matrix equation), which is solved without iteration at each time step.

This constraint-based control has been applied to the navigation control of multiagent, multi-swarm systems of double integrators, fully nonlinear quadrotor drones, and nonholonomic, differential drive, wheeled mobile robots subjected to actuator saturation, actuator dynamics, and external disturbances. Two types of constraints are considered for the aforementioned three types of systems: path following and collision avoidance constraints. Each constraint can be formulated based on vector norms or vector components and can be in either equality or inequality format. Thevector-component-based collision constraints lead to a natural byproduct of resolving deadlock in navigating swarms. Furthermore, through a partition of collision avoidance constraints among colliding agents, the control architecture for the navigation swarms can be centralized or decentralized. Numerical studies on swarms of double integrators, nonlinear quadrotor drones, and nonholonomic wheeled mobile robots have demonstrated the effectiveness and efficiency of the proposed approach.

Physical resection of tumors is a crucial component of the treatment of brain tumors. Traditionally, a multi-faceted approach involving resection as well as chemotherapy and radiation provide the backbone for most modern brain tumor treatment strategies. The process of tumor location and removal routinely involves the use of a number of sensory modalities (such as pre-operative MRIs and CT scans) and manual resection tools (such as electrocautery and forceps). Unfortunately, this current paradigm offers hurdles that stand in the way of more precise, accurate tumor resection. These hurdles include the physical phenomenon of brain shift and the natural limitation of the human hand placement in surgery. Due to the well documented relationship between extent of resection of brain tumor and survivability, there is a need to overcome these hurdles for more precise surgical resection. This dissertation presents a device that aims to increase the accuracy and precision of tumor removal surgery. This integrated system involves a non-contact laser induced fluorescence device, called the TumorID, and the previously documented TumorCNC. The TumorID utilizes a 405 nm laser to induce fluorescence that is collected by the device and quantified by an attached CCD spectrometer. The quantified spectral data is passed to a trained classifier that classifies the data as healthy or tumorous. The designation is passed to the TumorCNC. Based on the designation and sensory data, the TumorCNC generates an ablation path and removes tissue using a CO2 laser. The TumorID is capable of classifying melanoma brain metastasis, glioma, and healthy tissue with 100% accuracy based on ex vivo mouse brain tissue. The total integrated system is capable of ablating the boundary of a tumor mimicking tissue phantom with a RMSE of 1.69 mm. Therefore, on average for the entire tumor boundary, the device only deviates from the actual tumor boundary by approximately 1.5 mm. Reports have indicated that human surgeons can achieve accuracy on the order of approximately 0.3 mm. Therefore, the system is still short of the reported accuracy of a human surgeon. However, future research steps include the incorporation of a more sophisticated search strategy, implementation of a classifier that utilizes the boundary as a class in the mutli-class classifier, and decreasing the spot size of the CO2 laser. All of these potential avenues have the potential to increase the accuracy and precision of the tumor removal abilities of the non-contact, integrated system.

This dissertation proposes three control algorithms for active sensing with one or several autonomous robots.

The algorithms all rely on models of the information content of the sensor measurement with respect to the relative poses between sensors and subjects.

The approaches each predict how new information may impact the uncertainty in the subjects, controlling sensors to new locations or trajectories from where these uncertainties will me minimized.

The first algorithm deals with the Next-Best-View (NBV) problem for a single robot, where the goal is to control a mobile camera so that the next image of a set of possibly mobile targets will be as informative as possible.

The NBV controller is designed for a rig that hosts two cameras in a fronto-parallel arrangement, commonly known as stereo vision.

Assuming that the objects, landmarks, or targets being estimated are visible by both cameras in the rig and that these observations are corrupted by zero-mean Gaussian errors, the control algorithm moves the rig through pose space in order to reduce the expected Kalman-filtered uncertainty in the next location point-estimate.

This is done by differentiating the KF output error covariance matrix with respect to the sensor pose, which results in a nonlinear control problem.

The controller is decomposed so that first the robot computes the NBV in coordinates relative to the body-frame of the stereo rig, and then it moves in pose space to realize this view.

When an image is acquired, a switching signal changes the goal of pose control, giving rise to a stable hybrid system.

Experiments of on a real robot localizing targets in a laboratory setting are presented.

The second algorithm addresses the problem of estimating a finite set of hidden state vectors using a mobile robotic sensor network.

For every hidden state that needs to be estimated, a local Dynamic Program (DP) in the joint state-space of robot positions and state uncertainties determines robot paths and associated sequences of state observations that collectively minimize the estimation uncertainty.

It divides the collection of hidden states into clusters based on a prior belief of their geographic locations and, for each cluster, defines a second DP that determines how far along the local optimal trajectories the robot should travel before transitioning to estimating the next hidden state within the cluster.

Finally, a distributed assignment algorithm dynamically allocates controllers to the robot team from the set of optimal control policies at every cluster.

Assuming Gaussian priors on the hidden state vectors, the distributed state estimation method scales gracefully to large teams of mobile robots and hidden vectors and provide extensive simulations and real-world experiments using stereoscopic vision sensors to illustrate the approach.

The third chapter addresses the problem of controlling a network of mobile sensors so that a set of hidden states are estimated up to a user-specified accuracy. The sensors take measurements and fuse them online using an Information Consensus Filter (ICF). At the same time, the local estimates guide the sensors to their next best configuration. This leads to an LMI-constrained optimization problem that we solve by means of a new distributed random approximate projections method. The new method is robust to the state disagreement errors that exist among the robots as the ICF fuses the collected measurements. Assuming that the noise corrupting the measurements is zero-mean and Gaussian and that the robots are self localized in the environment, the integrated system converges to the next best positions from where new observations will be taken. This process is repeated with the robots taking a sequence of observations until the hidden states are estimated up to the desired user-specified accuracy. It presents simulations of sparse landmark localization, where the robotic team is achieves the desired estimation tolerances while exhibiting interesting emergent behavior.

Experiments of the first two algorithms are also presented.

The power of modern computer systems is due in no small part to their fantastic ability to adapt to whatever tasks they are charged with. Self-reconfigurable robots seek to provide that flexibility in hardware by building a system out of many individual modules, each with limited functionality, but with the ability to rearrange themselves to modify the shape and structure of the overall robotic system and meet whatever challenges are faced. Various hardware systems have been constructed for reconfigurable robots, and algorithms for them produce a wide variety of modes of locomotion. However, the task of efficiently controlling these complex systems -- possibly with thousands or millions of modules comprising a single robot -- is still not fully solved even after years of prior work on the topic.

In this thesis, we investigate the topic of theoretical control algorithms for lattice-style self-reconfigurable robots. These robots are composed of modules attached to each other in discrete lattice locations and only move by transitioning from one lattice location to another adjacent location. In our work, given the physical limitations of modules in a robot, we show a lower bound for the time to reconfiguration that robot. That is, transition the robot from one connected arrangement of modules to a different connected arrangement. Furthermore, we develop an algorithm with a running time that matches this lower bound both for a specific example reconfiguration problem and for general reconfiguration between any pair of 2D arrangements of modules. Since these algorithms match the demonstrated lower bound, they are optimal given the assumed abilities of the modules in the robot.

In addition to our theoretically optimal reconfiguration algorithms, we also make contributions to the more practical side of of this robotics field with a novel, physically stable control algorithm. The majority of prior theoretical work on control algorithms for self-reconfigurable robots did not consider the effects of gravity upon the robot. The result is that these algorithms often transform a robot into configurations -- arrangements of modules -- which are unstable and would likely break hardware on a real robot with thousands or millions of modules. In this thesis we present an algorithm for locomotion of a self-reconfigurable robot which is always physically stable in the presence of gravity even though we assume limited abilities for the robot's modules to withstand tension or sheer forces. This algorithm is highly scalable, able to be efficiently run on a robot with millions of modules, demonstrates significant speed advantages over prior scalable locomotion algorithms, and is resilient to errors in module actions or message passing. Overall, the contributions of this thesis extend both the theoretical and practical limits of what is possible with control algorithms for self-reconfigurable robots.

Swarm robotics and distributed control offer the promise of enhanced performance and robustness relative to that of individual and centrally-controlled robots, with decreased cost or time-to-completion for certain tasks. Having many degrees of freedom, swarm-related control and estimation problems are challenging specifically when the solutions depend on a great amount of communication among the robots. Swarm controllers minimizing communication requirements are quite desirable.

Swarms are inherently more robust to uncertainties and failures, including complete loss of individual agents, due to the averaging inherent in convergence and agreement problems. Exploitation of this robustness to minimize processing and communication complexity is desirable.

This research focuses on simple but robust controllers for swarming problems, maximizing the likelihood of objective success while minimizing controller complexity and specialized communication or sensing requirements.

In addition, it develops distributed solutions for swarm control by examining and exploiting graph theoretic constructs. Details of specific implementations, such as nonholonomic motion and and numerosity constraints, were explored with some unexpectedly positive results.

In summary, this research focused on the development of control strategies for the distributed control of a swarm of robots, and graph-theoretic analysis of these controllers. These control strategies specifically consider probabilistic connectivity functions, based on requirements for sensing or communication. The developed control strategies are validated in both simulation and experiment.

Wireless communication is known to play a pivotal role in enabling teams of robots to successfully accomplish global coordinated tasks. In fact, network connectivity is an underlying assumption in every distributed control and optimization algorithm. For this reason, in recent years, there is growing research in designing controllers that ensure point-to-point or end-to-end network connectivity for all time. Nevertheless, all these methods severely restrict the robots from accomplishing their tasks, as motion planning is always restricted by connectivity constraints on the network. Instead, a much preferred solution is to enable robots to communicate in an intermittent fashion, and operate in disconnect mode the rest of the time giving rise to an intermittently connected communication network. While in disconnect mode, the robots can accomplish their tasks free of communication constraints. The goal of this dissertation is to design a distributed intermittent connectivity framework that (i) ensures that the communication network is connected over time, infinitely often (ii) is flexible enough to account for arbitrary dynamic tasks, and (iii) can be applied to large-scale networks.

The great challenge in developing intermittent connectivity protocols for networks of mobile robots is to decide (i) which robots talk to which, (ii) where, and (iii) when, so that the communication network is connected over time infinitely often. To address these challenges, we decompose the network into small groups of robots, also called teams, so that every robot belongs to at least one team and that there is a path, i.e., a sequence of teams, where consecutive teams have non-empty intersections, connecting every two teams of robots, so that information can propagate in the network. First, given such fixed teams, we design infinite sequences of communication events for all robots, also called communication schedules, independent of the tasks assigned to the robots, that determine when every team should communicate, so that the communication network is connected over time infinitely often. The designed communication schedules ensure that all teams communicate infinitely often, i.e., that the communication network is connected over time infinitely often. Between communication events the robots can move in the workspace free of communication constraints to accomplish their assigned tasks. Theoretical guarantees and numerical experiments corroborate the proposed framework. This is the first distributed intermittent connectivity framework that can be applied to large-scale networks and is flexible enough to account for arbitrary dynamic robot tasks.

Next, given user-specified fixed teams, we integrate the respective communication schedules with task planning. Specifically, we consider high-level complex tasks captured by temporal logic formulas, state-estimation tasks, and time-critical dynamic tasks. The proposed distributed integrated path planning and intermittent connectivity frameworks determine both where and when every team should communicate so that the assigned task is accomplished, the communication network is connected over time infinitely often, and a user-specified metric, such as total traveled distance or consumed energy, is minimized. We show that employing the proposed intermittent connectivity framework for such tasks results in significant performance gains compared to the existing solutions in the literature that maintain connectivity for all time. Theoretical guarantees, numerical and experimental studies support the proposed distributed control algorithms.

Finally, we propose a fully autonomous intermittent connectivity framework that can handle arbitrary dynamic tasks and also allows the robots to locally and online update the structure of the teams and the communication schedules, effectively allowing them to decide who they should talk to, so that they can better accomplish newly assigned tasks. The structure of the teams, the associated communication locations, and the time instants when communication within teams will occur are integrated online with task planning giving rise to paths, i.e., sequences of waypoints, that ensure that the assigned task is accomplished, the communication network is connected over time infinitely often, and a user specified metric is minimized. This is the first fully autonomous, distributed, and

online intermittent connectivity framework that can handle arbitrary dynamic tasks and also controls the topology of the intermittently connected robot network to better accomplish these tasks. At the same time, the proposed framework scales well with the size of the robot network. Theoretical guarantees and numerical experiments corroborate the proposed distributed control scheme.

In this work, we address the problem of formal safety verification for stochastic cyber-physical systems (CPS) equipped with ReLU neural network (NN) controllers. Our goal is to find the set of initial states from where, with a predetermined confidence, the system will not reach an unsafe configuration within a specified time horizon. Specifically, we consider discrete-time LTI systems with Gaussian noise, which we abstract by a suitable graph. Then, we formulate a Satisfiability Modulo Convex (SMC) problem to estimate upper bounds on the transition probabilities between nodes in the graph. Using this abstraction, we propose a method to compute tight bounds on the safety probabilities of nodes in this graph, despite possible over-approximations of the transition probabilities between these nodes. Additionally, using the proposed SMC formula, we devise a heuristic method to refine the abstraction of the system in order to further improve the estimated safety bounds. Finally, we corroborate the efficacy of the proposed method with a robot navigation example and present comparative results with commonly employed verification schemes.

This thesis explores a few geometric optimization problems that arise

in robotics and sensor networks. In particular we present efficient

algorithms for the hitting-set problem and the budgeted hitting-set problem.

Given a set of objects and a collection of subsets of the objects,

called ranges, the hitting-set problem asks for a minimum number of

objects that intersect all the subsets in the collection.

In geometric settings, objects are

typically a set of points and ranges are defined by a set of geometric

regions (e.g., disks or polygons), i.e., the subset of points lying in each

region forms a range.

The first result of this thesis is an efficient algorithm for an instance

of the hitting-set problem in which both the set of points and the set

of ranges are implicitly defined. Namely, we are given a convex

polygonal robot and a set of convex polygonal obstacles, and we wish

to find a small number of congruent copies of the robot that intersect

all the obstacles.

Next, motivated by the application of sensor placement in sensor networks,

we study the so-called ``art-gallery'' problem. Given a polygonal

environment, we wish to place the minimum number of guards so that

the every point in the environment is visible from at least one guard.

This problem can be formulated as a hitting-set problem. We present

a sampling based algorithm for this problem and study various extensions

of this problem.

Next, we study the geometric hitting-set problem in a dynamic setting,

where the objects and/or the ranges change with time and the goal is

to maintain a hitting set. We present algorithms

which maintain a small size hitting set with sub-linear update time.

Finally, we consider the budgeted hitting-set problem, in which we

are asked to choose a bounded number of objects that intersect as many

ranges as possible. Motivated by applications in network vulnerability

analysis we study this problem in a probabilistic setting.

During my PhD journey, I have lived at the intersection of a previous military career, leadership as an elected official, and a student passionate about robotics and protecting our beautiful coastal ecosystem. As a non-traditional student, Duke University has presented me with experiences I could not have imagined. With the Duke Marine Robotics and Remote Sensing (MaRRS) Lab drones, I have had the opportunity to survey the mass nesting of thousands of olive ridley sea turtles in Costa Rica, hundreds of gray seals in Massachusetts, endangered right whales off the coast of Florida, dozens of World War I shipwrecks in Maryland, Etruscan and Roman archeological sites in Italy, and hundreds of seals in the Bering Sea. And there have been many more multi-domain surveys of our glorious coastal ecosystem in Carteret County. There have been more than our fair share of challenges during this time frame to include preparing and responding to Hurricanes Florence, Dorian, and Isaias, plus the COVID-19 pandemic. These events took a toll on many fronts, but also presented leadership opportunities. With our drones, we have been able to survey before and after storms, and we’re watching barrier islands move at centimeter scale. The increasing effects of climate change are very personal for those of us living in eastern North Carolina, but in the MaRRS Lab we are well postured with our robotics to air-, sea-, and ground-truth these effects. Perhaps most importantly, the knowledge I gained during my PhD program informed my policy positions during my tenure as the Mayor of the Town of Beaufort, NC. I am very proud of the progress that we made to include a massive clean-up of our waterways following Hurricane Florence, a Harbor Management Ordinance to better manage our waterways, expanded municipal jurisdiction to further manage our ecosystem, unprecedented repairs of infrastructure that were neglected for decades and have negatively affected our water quality, investment in the community, and a five-year budgeting plan to provide greater stability for Beaufort.

This dissertation is a summation of some of the work performed during my Duke PhD experience. In Chapter 1, I describe the evolution of autonomous drones, define distinct generations of this technology, and articulate the negative impacts of a regulatory system that is stifling critical research. For Chapter 2, I discuss the lexicon, taxonomy, and ontology of small autonomous drones, the critical importance of situational awareness, and a framework of considerations and best practices for those interested in pursuing autonomous mobile robots to enhance their research. With Chapters 1 and 2 as a foundation, I next highlight my expansion to the marine domain for water quality research with autonomous surface vessels (Chapter 3) and multi-disciplinary archeological drone surveys in Vulci, Italy (Chapter 4). Finally in Chapter 5, I address scientific research that informed policy successes during my time as a mayor and PhD student. What a great journey!

In this paper, we consider robot navigation problems in environments populated by humans. The goal is to determine collision-free and dynamically feasible trajectories that also maximize human satisfaction, by ensuring that robots are available to assist humans with their work as needed and avoid actions that cause discomfort. In practice, human satisfaction is subjective and hard to describe mathematically. As a result, the planning problem we consider in this paper may lack important contextual information. To address this challenge, we propose a semi-supervised Bayesian Optimization (BO) method to design globally optimal robot trajectories using bandit human feedback, in the form of complaints or satisfaction ratings, that expresses how desirable a trajectory is. Since trajectory planning is typically a high-dimensional optimization problem in the space of waypoints that need to be decided, BO may require prohibitively many queries for human feedback to return a good solution. To this end, we use an autoencoder to reduce the high-dimensional space into a low dimensional latent space, which we update using human feedback. Moreover, we improve the exploration efficiency of BO by biasing the search for new trajectories towards dynamically feasible and collision-free trajectories obtained using off-the-shelf motion planners. We demonstrate the efficiency of our proposed trajectory planning method in a scenario with humans that have diversified and unknown demands.