Author name cluster

Howie Choset

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

202 papers

2 author rows

ICRA Conference 2025 Conference Paper

A Complete and Bounded-Suboptimal Algorithm for a Moving Target Traveling Salesman Problem with Obstacles in 3D

Anoop Bhat
Geordan Gutow
Bhaskar Vundurthy
Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

The moving target traveling salesman problem with obstacles (MT-TSP-O) seeks an obstacle-free trajectory for an agent that intercepts a given set of moving targets, each within specified time windows, and returns to the agent's starting position. Each target moves with a constant velocity within its time windows, and the agent has a speed limit no smaller than any target's speed. We present FMC*-TSP, the first complete and bounded-suboptimal algorithm for the MT-TSP-O, and results for an agent whose configuration space is $\mathbb{R}^{3}$. Our algorithm interleaves a high-level search and a lowlevel search, where the high-level search solves a generalized traveling salesman problem with time windows (GTSP-TW) to find a sequence of targets and corresponding time windows for the agent to visit. Given such a sequence, the low-level search then finds an associated agent trajectory. To solve the low-level planning problem, we develop a new algorithm called FMC*, which finds a shortest path on a graph of convex sets (GCS) via implicit graph search and pruning techniques specialized for problems with moving targets. We test FMC*-TSP on 280 problem instances with up to 40 targets and demonstrate its smaller median runtime than a baseline based on prior work.

IROS Conference 2025 Conference Paper

Bag-of-Word-Groups (BoWG): A Robust and Efficient Loop Closure Detection Method Under Perceptual Aliasing

Xiang Fei
Tina Tian
Howie Choset
Lu Li

Loop closure is critical in Simultaneous Localization and Mapping (SLAM) systems to reduce accumulative drift and ensure global mapping consistency. However, conventional methods struggle in perceptually aliased environments, such as narrow pipes, due to vector quantization, feature sparsity, and repetitive textures, while existing solutions often incur high computational costs. This paper presents Bag-of-Word-Groups (BoWG), a novel loop closure detection method that achieves superior precision-recall, robustness, and computational efficiency. The core innovation lies in the introduction of word groups, which captures the spatial co-occurrence and proximity of visual words to construct an online dictionary. Additionally, drawing inspiration from probabilistic transition models, we incorporate temporal consistency directly into similarity computation with an adaptive scheme, substantially improving precision-recall performance. The method is further strengthened by a feature distribution analysis module and dedicated post-verification mechanisms. To evaluate the effectiveness of our method, we conduct experiments on both public datasets and a confined-pipe dataset we constructed. Results demonstrate that BoWG surpasses state-of-the-art methods—including both traditional and learning-based approaches—in terms of precision-recall and computational efficiency. Our approach also exhibits excellent scalability, achieving an average processing time of 16 ms per image across 17, 565 images in the Bicocca25b dataset. The source code is available at: https://github.com/EdgarFx/BoWG.

ICRA Conference 2025 Conference Paper

Bio-Inspired Distributed Neural Locomotion Controller (D-NLC) for Robust Locomotion and Emergent Behaviors

Zhikai Zhang
Siqi Guo
Henry Kou
Ishayu Shikhare
Howie Choset
Lu Li

Despite having fewer neurons than more complex life forms, insects are still capable of producing astonishing locomotive behaviors, such as traversing diverse environments and making rapid gait adaptations after extreme injury or autotomy. Biologists attribute this to a chain of segmental neuron clusters (ganglia) within insect nervous systems, which act as distributed self-organizing sensorimotor control units. Inspired by the neural structure of the Carausius morosus, the common stick insect, this work introduces the Distributed Neural Locomotion Controller (D-NLC), a modular control framework that utilizes local proprioceptive feedback to modulate joint-level Central Pattern Generator (CPG) signals to produce emergent locomotive behaviors. This framework was implemented on a modular legged robot with distributed jointlevel embedded computing units. In addition, assessments were conducted on the framework's performance and behavior in various experimental settings. Based on real-world experiments, we observe an overall 31. 3% average increase in curvilinear motion performance under external (terrain) and internal (amputation) perturbation compared to a centralized predefined gait controller. This difference is statistically significant $(P \ll 0. 05)$ for larger perturbations but not for single-leg amputations. Experiments with perturbation-induced leg stance duration and leg phase-difference analysis further validated our hypothesis regarding D-NLC's role in the robust perceptive locomotion and self-emergent gait adaptation against complex unforeseen perturbations. This proposed control framework does not require any numerical optimization or weight training processes, which are time-consuming and computationally expensive. To the best of our knowledge, this framework is the first bio-inspired neural controller deployed on a distributed embedded system. More info at https://eigenbot-dnlc.github.io.

ICRA Conference 2025 Conference Paper

Efficient Second-Order Cone Programming for the Close Enough Traveling Salesman Problem

Geordan Gutow
Howie Choset

When agents must execute multiple tasks at spatially distinct locations, it is common to formulate and solve a Traveling Salesman Problem (TSP) to find the order of locations (targets) that requires the smallest travel cost. Approaching such task sequencing problems as a TSP is restrictive, as it requires that unique locations be specified for each task. In reality a set of acceptable locations might be available. The Close Enough Traveling Salesman Problem (CETSP) is a generalization of the Traveling Salesman Problem in which the agent needs only visit a spherical neighborhood surrounding each target, and can thus address this task sequencing problem when any location in a sphere is acceptable. Prior work has developed a branch-and-bound approach that finds globally optimal solutions to instances of the CETSP by solving a sequence of Second-Order Cone Programs (SOCP). We demonstrate it is possible to eliminate $2 / 3$ of the variables and $1 / 2$ of the constraints in these SOCPs, show how to reuse computation and memory allocation across multiple SOCPs in the sequence, and propose a strategy to warm-start the SOCPs using solutions obtained earlier in the sequence. Collectively, these three changes halve the time required to solve 210 random CETSP instances to optimality. We also obtained improved lower bounds on 73 instances from the literature, including solving one instance to optimality for the first time.

AIJ Journal 2025 Journal Article

EMOA*: A framework for search-based multi-objective path planning

Zhongqiang Ren
Carlos Hernández
Maxim Likhachev
Ariel Felner
Sven Koenig
Oren Salzman
Sivakumar Rathinam
Howie Choset

In the Multi-Objective Shortest Path Problem (MO-SPP), one has to find paths on a graph that simultaneously minimize multiple objectives. It is not guaranteed that there exists a path that minimizes all objectives, and the problem thus aims to find the set of Pareto-optimal paths from the start to the goal vertex. A variety of multi-objective A*-based search approaches have been developed for this purpose. Typically, these approaches maintain a front set at each vertex during the search process to keep track of the Pareto-optimal paths that reach that vertex. Maintaining these front sets becomes burdensome and often slows down the search when there are many Pareto-optimal paths. In this article, we first introduce a framework for MO-SPP with the key procedures related to the front sets abstracted and highlighted, which provides a novel perspective for understanding the existing multi-objective A*-based search algorithms. Within this framework, we develop two different, yet closely related approaches to maintain these front sets efficiently during the search. We show that our approaches can find all cost-unique Pareto-optimal paths, and analyze their runtime complexity. We implement the approaches and compare them against baselines using instances with three, four and five objectives. Our experimental results show that our approaches run up to an order of magnitude faster than the baselines.

ICRA Conference 2025 Conference Paper

Ergodic Exploration over Meshable Surfaces

Dayi Dong
Albert Xu
Geordan Gutow
Howie Choset
Ian Abraham

Robotic search and rescue, exploration, and inspection require trajectory planning across a variety of domains. A popular approach to trajectory planning for these types of missions is ergodic search, which biases a trajectory to spend time in parts of the exploration domain that are believed to contain more information. Most prior work on ergodic search has been limited to searching simple surfaces, like a 2D Euclidean plane or a sphere, as they rely on projecting functions defined on the exploration domain onto analytically obtained Fourier basis functions. In this paper, we extend ergodic search to any surface that can be approximated by a triangle mesh. The basis functions are approximated through finite element methods on a triangle mesh of the domain. We formally prove that this approximation converges to the continuous case as the mesh approximation converges to the true domain. We demonstrate that on domains where analytical basis functions are available (plane, sphere), the proposed method obtains equivalent results, and while on other domains (torus, bunny, wind turbine), the approach is versatile enough to still search effectively. Lastly, we also compare with an existing ergodic search technique that can handle complex domains and show that our method results in a higher quality exploration.

IROS Conference 2025 Conference Paper

Mixed Integer Conic Programming for Multi-Agent Motion Planning in Continuous Space

Shizhe Zhao
Yongce Liu
Howie Choset
Zhongqiang Ren

Multi-Agent Motion Planning (MAMP) seeks collision-free trajectories for multiple agents from their respective start to goal locations among static obstacles, while minimizing a cost function over the trajectories. Existing approaches for this problem include graph-based, Mix-Integer Programming (MIP) based and trajectory optimization-based, each with its own limitations. This paper introduces a new approach for MAMP based on Mixed Integer Conic Programming (MICP) formulation that complements these existing approaches. We show that our formulation is valid and test our approach against various baselines, including a graph-based method that combines search and sampling, as well as different MIP formulations. The numerical results show that the solutions found by our approach are sometimes eight times closer to the true optimum than the ones found by the baseline when given the same amount of runtime limit. We also verify our approach with multiple drones in a lab setting.

ICRA Conference 2025 Conference Paper

Multi-Agent Ergodic Exploration Under Smoke-Based Time-Varying Sensor Visibility Constraints

Elena Wittemyer
Ananya Rao
Ian Abraham
Howie Choset

In this work, we consider the problem of multiagent informative path planning (IPP) for robots whose sensor visibility continuously changes as a consequence of a time-varying natural phenomenon. We leverage ergodic trajectory optimization (ETO), which generates paths such that the amount of time an agent spends in an area is proportional to the expected information in that area. We focus specifically on the problem of multi-agent drone search of a wildfire, where we use the time-varying environmental process of smoke diffusion to construct a sensor visibility model. This sensor visibility model is used to repeatedly calculate an expected information distribution (EID) to be used in the ETO algorithm. Our experiments show that our exploration method achieves improved information gathering over both baseline search methods and naive ergodic search formulations.

ICRA Conference 2025 Conference Paper

Propagative Distance Optimization for Motion Planning

Yu Chen
Jinyun Xu
Yilin Cai
Ting-Wei Wong
Zhongqiang Ren
Howie Choset
Guanya Shi

This paper focuses on the motion planning problem for serial articulated robots with revolute joints under kinematic constraints. Many motion planners leverage iterative local optimization methods but are often trapped in local minima due to non-convexity of the problem. A key reason for the non-convexity is the trigonometric term when parameterizing the kinematics using joint angles. Recent distance-based formulations can eliminate these trigonometric terms by formulating the kinematics based on distances, and has shown superior performance against classic joint angle based formulations in domains like inverse kinematics (IK). However, distance-based kinematics formulations have not yet been studied for motion planning, and naively applying them for motion planning may lead to poor computational efficiency. In particular, IK seeks one configuration while motion planning seeks a sequence of configurations, which greatly increases the scale of the underlying optimization problem. This paper proposes Propagative Distance Optimization for Motion Planning (PDOMP), which addresses the challenge by (i) introducing a new compact representation that reduces the number of variables in the distance-based formulation, and (ii) leveraging the chain structure to efficiently compute forward kinematics and Jacobians of the robot among waypoints along a path. Test results show that PDOMP runs up to 10 times faster than the sampling-based and angle-based-optimization baseline methods.

ICRA Conference 2025 Conference Paper

Wavelet-Based Distributed Coverage for Heterogeneous Agents

Ananya Rao
Howie Choset
David Wettergreen

We develop a coverage approach for heterogeneous agents that leverages the different sensing and motion capabilities of a team. Coverage performance is measured using ergodicity, which when optimized balances exploitation versus exploration, where areas of interest are indicated with an information metric. Prior work uses spectral decomposition of a spatial map of information to guide a set of heterogeneous agents, each with different sensor and motion models, to optimize coverage. This work leverages wavelet transforms to decompose the information map rather than the Fourier transform typically applied to ergodic search and demonstrates the importance of selecting a suitable wavelet family to use, based on the information map being explored. Further a sequence of wavelets is used for decomposition to overcome dependency on selecting one suitable wavelet family. Our experimental results show that using wavelet families well-suited to the specific information map for information map decomposition leads to, on average, 43% improvement over a baseline method in terms of a standard coverage metric (ergodicity), while using a wellsequenced set of wavelets for decomposition leads to a 65% improvement in coverage performance across multiple types of information maps.

IROS Conference 2024 Conference Paper

A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets

Allen George Philip
Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP), which seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot. The formulation relies on the key idea that when the targets move along lines, their trajectories become convex sets within the space-time coordinate system. The problem then reduces to finding the shortest path within a graph of convex sets, subject to some speed constraints. We compare our formulation with the current state-of-the-art Mixed Integer Conic Program (MICP) formulation for the MT-TSP. The experimental results show that our formulation outperforms the MICP for instances with up to 20 targets, with up to two orders of magnitude reduction in runtime, and up to a 60% tighter optimality gap. We also show that the solution cost from the convex relaxation of our formulation provides significantly tighter lower-bounds for the MT-TSP than the ones from the MICP.

RLC Conference 2024 Conference Paper

Assigning Credit with Partial Reward Decoupling in Multi-Agent Proximal Policy Optimization

Aditya Kapoor
Benjamin Freed
Jeff Schneider
Howie Choset

Multi-agent proximal policy optimization (MAPPO) has recently demonstrated state-of-the-art performance on challenging multi-agent reinforcement learning tasks. However, MAPPO still struggles with the credit assignment problem, wherein the sheer difficulty in ascribing credit to individual agents' actions scales poorly with team size. In this paper, we propose a multi-agent reinforcement learning algorithm that adapts recent developments in credit assignment to improve upon MAPPO. Our approach leverages partial reward decoupling (PRD), which uses a learned attention mechanism to estimate which of a particular agent's teammates are relevant to its learning updates. We use this estimate to dynamically decompose large groups of agents into smaller, more manageable subgroups. We empirically demonstrate that our approach, PRD-MAPPO, decouples agents from teammates that do not influence their expected future reward, thereby streamlining credit assignment. We additionally show that PRD-MAPPO yields significantly higher data efficiency and asymptotic performance compared to both MAPPO and other state-of-the-art methods across several multi-agent tasks, including StarCraft II. Finally, we propose a version of PRD-MAPPO that is applicable to \textit{shared} reward settings, where PRD was previously not applicable, and empirically show that this also leads to performance improvements over MAPPO.

RLJ Journal 2024 Journal Article

Assigning Credit with Partial Reward Decoupling in Multi-Agent Proximal Policy Optimization

Aditya Kapoor
Benjamin Freed
Jeff Schneider
Howie Choset

Multi-agent proximal policy optimization (MAPPO) has recently demonstrated state-of-the-art performance on challenging multi-agent reinforcement learning tasks. However, MAPPO still struggles with the credit assignment problem, wherein the sheer difficulty in ascribing credit to individual agents' actions scales poorly with team size. In this paper, we propose a multi-agent reinforcement learning algorithm that adapts recent developments in credit assignment to improve upon MAPPO. Our approach leverages partial reward decoupling (PRD), which uses a learned attention mechanism to estimate which of a particular agent's teammates are relevant to its learning updates. We use this estimate to dynamically decompose large groups of agents into smaller, more manageable subgroups. We empirically demonstrate that our approach, PRD-MAPPO, decouples agents from teammates that do not influence their expected future reward, thereby streamlining credit assignment. We additionally show that PRD-MAPPO yields significantly higher data efficiency and asymptotic performance compared to both MAPPO and other state-of-the-art methods across several multi-agent tasks, including StarCraft II. Finally, we propose a version of PRD-MAPPO that is applicable to \textit{shared} reward settings, where PRD was previously not applicable, and empirically show that this also leads to performance improvements over MAPPO.

IROS Conference 2024 Conference Paper

GESCE: Graph-based Ergodic Search in Cluttered Environments

Burhanuddin Shirose
Adam Johnson
Bhaskar Vundurthy
Howie Choset
Matthew Travers

In this paper, we present a novel motion planning algorithm that inherits the strengths of both optimization and search-based planners. Optimization-based planners use the gradient of an objective function to generate a desired path, whereas search-based planners operate on a graph capturing the salient topology of a robot’s free space. A class of optimization-based planners leverages prior information, modeled as a probability distribution of target locations in an environment, to guide path generation. We embrace one specific measure, referred to as ergodicity, which encourages a robot to spend a proportion of its time, weighted by the distribution, where it is likely to find targets of interest. Methods that minimize ergodicity were not designed to handle obstacles in the environment, and augmented approaches that add "soft" constraints for obstacles to the cost function may still yield a path that collides with an obstacle. In this work, we present a hybrid approach that first generates a graph of the environment’s free space, followed by searching the graph with ergodicity as a heuristic. Our approach not only restricts the search to the free space, thereby avoiding obstacles by design, but also generates trajectories with low ergodicity values. Extensive testing on 125 test scenarios with varying degrees of clutter, information distribution, and robot start locations illustrate the efficacy of our algorithm.

SoCS Conference 2024 Conference Paper

Heuristic Search for the Orienteering Problem with Time-Varying Reward

Chao Cao
Jinyun Xu
Ji Zhang 0003
Howie Choset
Zhongqiang Ren

The Orienteering Problem (OP) seeks a path on a graph to maximize total rewards collected subject to a path length budget. Typically, a reward is achieved by visiting a vertex in the graph, and such a reward is constant for all time. This paper considers a variant of OP where the reward of each vertex is an arbitrary time-dependent function, and hence the name time-varying reward OP (TR-OP). To solve this problem, we develop a novel heuristic search algorithm called Reward Maximization A* (RMA*), which is guaranteed to find an optimal solution to TR-OP. We also develop a fast method to compute an admissible heuristic for RMA* that can effectively direct the search to save computational effort. Furthermore, we introduce a hyper-parameter in RMA* that trades off between solution quality and runtime efficiency for RMA*. We benchmark RMA* against a recent dynamic programming (DP) approach, which runs fast in practice, but has no guarantee of the solution optimality. In our tests, RMA* reduces the runtime by up to 70% compared to DP. By adjusting the hyper-parameter, RMA* is able to find solutions with up to 30% more rewards than those found by DP.

ICRA Conference 2024 Conference Paper

Hierarchical Planning for Long-Horizon Multi-Agent Collective Construction

Shambhavi Singh
Zejian Huang
Akshaya Kesarimangalam Srinivasan
Geordan Gutow
Bhaskar Vundurthy
Howie Choset

We develop a planner that directs robots to construct a 3D target structure composed of blocks. The robots themselves are cubes of the same size as the blocks, and they may place, carry, or remove one block at a time. When moving, robots are also allowed to climb or descend a block. A construction plan may thus build a staircase-like scaffolding of blocks to reach other blocks at higher levels. The order of block placement is important; for example, a block that sits atop other blocks must be placed after the blocks below it, and a block that needs scaffolding cannot be placed until after the scaffolding is. Prior works focus on end-to-end approaches that simultaneously plan for block placement order and inter-robot collisions. Larger structures are either intractable or yield high-cost solutions. A prior approach mitigates this by decomposing the structure into smaller components that can be planned for independently, but the computational challenge remains. We present a hierarchical approach that first 1) uses A* to determine a sequence of block placements and removals while ignoring inter-robot collision, then 2) identifies ordering constraints between block placement and removal actions, and finally (3) computes collision-free paths for multiple robots to perform said actions. Compared to an optimization approach that minimizes the number of timesteps to complete the structure, we observe a 100x reduction in computation time for comparable solutions.

ICRA Conference 2024 Conference Paper

Learning Heterogeneous Multi-Agent Allocations for Ergodic Search

Ananya Rao
Guillaume Sartoretti
Howie Choset

Information-based coverage directs robots to move over an area to optimize a pre-defined objective function based on some measure of information. Our prior work determined that the spectral decomposition of an information map can be used to guide a set of heterogeneous agents, each with different sensor and motion models, to optimize coverage in a target region, based on a measure called ergodicity. In this paper, we build on this insight to construct a reinforcement learning formulation of the problem of allocating heterogeneous agents to different search regions in the frequency domain. We relate the spectral coefficients of the search map to each other in three different ways. The first method maps agents to predefined sets of spectral coefficients. In the second method, each agent learns a weight distribution over all spectral coefficients. Finally, in the third method, each agent learns weight distributions as parameterized curves over coefficients. Our numerical results demonstrate that distributing and assigning coverage responsibilities to agents depending on their sensing and motion models leads to 40%, 51%, and 46% improvement in coverage performance as measured by the ergodic metric, and 15%, 22%, and 20% improvement in time to find all targets in the search region, for the three methods respectively.

ICLR Conference 2024 Conference Paper

Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem

Albert Xu
Jhih-Yi Hsieh
Bhaskar Vundurthy
Nithya Kemp
Eliana Cohen
Lu Li
Howie Choset

In deep metric learning, the triplet loss has emerged as a popular method to learn many computer vision and natural language processing tasks such as facial recognition, object detection, and visual-semantic embeddings. One issue that plagues the triplet loss is network collapse, an undesirable phenomenon where the network projects the embeddings of all data onto a single point. Researchers predominately solve this problem by using triplet mining strategies. While hard negative mining is the most effective of these strategies, existing formulations lack strong theoretical justification for their empirical success. In this paper, we utilize the mathematical theory of isometric approximation to show an equivalence between the triplet loss sampled by hard negative mining and an optimization problem that minimizes a Hausdorff-like distance between the neural network and its ideal counterpart function. This provides the theoretical justifications for hard negative mining's empirical efficacy. Experiments performed on the Market-1501 and Stanford Online Products datasets with various network architectures corroborate our theoretical findings, indicating that network collapse tends to happen when batch size is too large or embedding dimension is too small. In addition, our novel application of the isometric approximation theorem provides the groundwork for future forms of hard negative mining that avoid network collapse.

IROS Conference 2024 Conference Paper

PINSAT: Parallelized Interleaving of Graph Search and Trajectory Optimization for Kinodynamic Motion Planning

Ramkumar Natarajan
Shohin Mukherjee
Howie Choset
Maxim Likhachev

Trajectory optimization is a widely used technique in robot motion planning for letting the dynamics of the system shape and synthesize complex behaviors. Several previous works have shown its benefits in high-dimensional continuous state spaces and under differential constraints. However, long time horizons and planning around obstacles in non-convex spaces pose challenges in guaranteeing convergence or finding optimal solutions. As a result, discrete graph search planners and sampling-based planers are preferred when facing obstacle-cluttered environments. A recently developed algorithm called INSAT effectively combines graph search in the low-dimensional subspace and trajectory optimization in the full-dimensional space for global kinodynamic planning over long horizons. Although INSAT successfully reasoned about and solved complex planning problems, the numerous expensive calls to an optimizer resulted in large planning times, thereby limiting its practical use. Inspired by the recent work on edge-based parallel graph search, we present PINSAT, which introduces systematic parallelization in INSAT to achieve lower planning times and higher success rates, while maintaining significantly lower costs over relevant baselines. We demonstrate PINSAT by evaluating it on 6 DoF kinodynamic manipulation planning with obstacles. We demonstrate PINSAT by evaluating it on two kinodynamic manipulation planning scenarios: (i) a single ball blocking task among obstacles using a 6 DoF ABB arm, and (ii) a multi-ball blocking task where the balls are separated by short time intervals using a 7 DoF KUKA LBR iiwa arm with obstacles.

ICRA Conference 2024 Conference Paper

Preprocessing-based Kinodynamic Motion Planning Framework for Intercepting Projectiles using a Robot Manipulator

Ramkumar Natarajan
Hanlan Yang
Qintong Xie
Yash Oza
Manash Pratim Das
Fahad Islam 0002
Muhammad Suhail Saleem
Howie Choset

We are interested in studying sports with robots and starting with the problem of intercepting a projectile moving toward a robot manipulator equipped with a shield. To successfully perform this task, the robot needs to (i) detect the incoming projectile, (ii) predict the projectile’s future motion, (iii) plan a minimum-time rapid trajectory that can evade obstacles and intercept the projectile, and (iv) execute the planned trajectory. These four steps must be performed under the manipulator’s dynamic limits and extreme time constraints (≤ 350ms in our setting) to successfully intercept the projectile. In addition, we want these trajectories to be smooth to reduce the robot’s joint torques and the impulse on the platform on which it is mounted. To this end, we propose a kinodynamic motion planning framework that preprocesses smooth trajectories offline to allow real-time collision-free executions online. We present an end-to-end pipeline along with our planning framework, including perception, prediction, and execution modules. We evaluate our framework experimentally in simulation and show that it has a higher blocking success rate than the baselines. Further, we deploy our pipeline on a robotic system comprising an industrial arm (ABB IRB-1600) and an onboard stereo camera (ZED 2i), which achieves a 78% success rate in projectile interceptions.

RLJ Journal 2024 Journal Article

Unifying Model-Based and Model-Free Reinforcement Learning with Equivalent Policy Sets

Benjamin Freed
Thomas Wei
Roberto Calandra
Jeff Schneider
Howie Choset

Model-based and model-free reinforcement learning (RL) each possess relative strengths that prevent either algorithm from strictly outperforming the other. Model-based RL often offers greater data efficiency, as it can use models to evaluate many possible behaviors before choosing one to enact. However, because models cannot perfectly represent complex environments, agents that rely too heavily on models may suffer from poor asymptotic performance. Model-free RL, on the other hand, avoids this problem at the expense of data efficiency. In this work, we seek a unified approach to RL that combines the strengths of both approaches. To this end, we introduce the concept of _equivalent policy sets_ (EPS), which quantify the limitations of models for the purposes of decision-making, _i.e._, action selection. Based on this concept, we propose _Unified RL_, a novel RL algorithm that uses models to constrain model-free RL to the set of policies that are not provably suboptimal, according to model-based bounds on policy performance. We demonstrate across a range of benchmarks that Unified RL effectively combines the relative strengths of both model-based and model-free RL, in that it achieves comparable data efficiency to model-based RL, while achieving asymptotic performance similar or superior to that of model-free RL. Additionally, we show that Unified RL often outperforms a number of existing state-of-the-art model-based and model-free RL algorithms, and _can learn effective policies in situations where either model-based or model-free RL alone fail_.

RLC Conference 2024 Conference Paper

Unifying Model-Based and Model-Free Reinforcement Learning with Equivalent Policy Sets

Benjamin Freed
Thomas Wei
Roberto Calandra
Jeff Schneider
Howie Choset

Model-based and model-free reinforcement learning (RL) each possess relative strengths that prevent either algorithm from strictly outperforming the other. Model-based RL often offers greater data efficiency, as it can use models to evaluate many possible behaviors before choosing one to enact. However, because models cannot perfectly represent complex environments, agents that rely too heavily on models may suffer from poor asymptotic performance. Model-free RL, on the other hand, avoids this problem at the expense of data efficiency. In this work, we seek a unified approach to RL that combines the strengths of both approaches. To this end, we introduce the concept of _equivalent policy sets_ (EPS), which quantify the limitations of models for the purposes of decision-making, _i. e. _, action selection. Based on this concept, we propose _Unified RL_, a novel RL algorithm that uses models to constrain model-free RL to the set of policies that are not provably suboptimal, according to model-based bounds on policy performance. We demonstrate across a range of benchmarks that Unified RL effectively combines the relative strengths of both model-based and model-free RL, in that it achieves comparable data efficiency to model-based RL, while achieving asymptotic performance similar or superior to that of model-free RL. Additionally, we show that Unified RL often outperforms a number of existing state-of-the-art model-based and model-free RL algorithms, and _can learn effective policies in situations where either model-based or model-free RL alone fail_.

ICRA Conference 2023 Conference Paper

A Curvature and Trajectory Optimization-based 3D Surface Reconstruction Pipeline for Ultrasound Trajectory Generation

Ananya Bal
Ashutosh Gupta 0004
Abhimanyu
John M. Galeotti
Howie Choset

Ultrasound scanning is an efficient imaging modality preferred for quick medical procedures. However, due to the lack of skilled sonographers, researchers have developed many Robotic Ultrasound System (RUS) prototypes for various procedures. Most of these systems have a human-in-the-loop and require an expert to point the robot to the region of the subject to be scanned. Only a few systems try to incorporate some knowledge from the exterior shape of the subject for ultrasound scanning. Accurate 3D surface reconstruction of a patient's exterior can enable an RUS to perceive subjects more like a clinician would. It can help localize the subject for the robot while eliminating input from an expert. Ultrasound scanning trajectories can be better planned if the RUS first detects critical regions on the surface of the subject and corresponding curvatures. We use an RGB-D sensor to acquire point clouds representing the 3D surface of the subject, which in the present work is for a lower-torso leg phantom. A consolidated pipeline for creating an optimized 3D surface reconstruction of a subject is presented and is used to autonomously identify a region of interest for scanning femoral vessels with an ultrasound probe. To make our system more robust to inter-subject variations in shape and size, we incorporate a trajectory optimization module of the RUS-mounted RGB-D sensor. To this end, we introduce a comprehensive evaluation score to quantify the quality of point cloud reconstructions. The resulting improvements in 3D surface scanning and reconstruction enable near-automation in generating ultrasound scanning trajectories for femoral vessels. Our pipeline produces ultrasound images with an average ZNCC score of 0. 86 and our 3D point cloud reconstructions are accurate up to le-5 m from a ground-truth high-resolution CT scan.

ICAPS Conference 2023 Conference Paper

Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding

Zhongqiang Ren
Jiaoyang Li 0001
Han Zhang 0018
Sven Koenig
Sivakumar Rathinam
Howie Choset

This paper considers a multi-agent multi-objective path-finding problem that requires not only finding collision-free paths for multiple agents from their respective start locations to their respective goal locations but also optimizing multiple objectives simultaneously. In general, there is no single solution that optimizes all the objectives simultaneously, and the problem is thus to find the so-called Pareto-optimal frontier. To solve this problem, an algorithm called Multi-Objective Conflict-Based Search (MO-CBS) was recently developed and is guaranteed to find the exact Pareto-optimal frontier. However, MO-CBS does not scale well with the number of agents due to the large branching factor of the search, which leads to a lot of duplicated effort in agent-agent collision resolution. This paper therefore develops a new algorithm called Binary Branching MO-CBS (BB-MO-CBS) that reduces the branching factor as well as the duplicated collision resolution during the search, which expedites the search as a result. Our experimental results show that BB-MO-CBS reduces the number of conflicts by up to two orders of magnitude and often doubles or triples the success rates of MO-CBS on various maps given a runtime limit.

IROS Conference 2023 Conference Paper

EELS: Towards Autonomous Mobility in Extreme Terrain with a Versatile Snake Robot with Resilience to Exteroception Failures

Rohan Thakker
Michael Paton
Marlin P. Strub
R. Michael Swan
Guglielmo Daddi
Rob Royce
L. Phillipe Tosi
Matthew Gildner

The discovery of ocean worlds such as Enceladus, Titan, and Europa motivates the development of versatile autonomous mobility systems to enable the next era of space exploration where there is large uncertainty in terrain specifications due to a lack of prior surface reconnaissance missions. To explore these environments, we propose Exobiology Extant Life Surveyor (EELS): the first large-scale (4 lm long with 400 Nm peak torque) snake robot. The large scale is achieved by using a screw-based active skin mechanism to decouple motion and shape control. Autonomous mobility for such a system remains an open problem due to its many Degrees of Freedom (DoFs), complex terrain interactions, and intermittent localization failures in GPS-denied perceptually degraded environments due to the presence of fog, dust, featureless terrains, etc. We propose NEO, an autonomy architecture that scales to large DoFs to generate a versatile set of gaits to achieve mobility in unknown extreme environments. We also discuss the resilience capabilities of NEO that achieves closed-loop tracking performance by leveraging exteroception when available but can also operate with proprioception only, leading to resiliency against localization failures via graceful degradation in performance rather than unsafe behaviors. A quantitative hardware evaluation of exteroceptive leader-follower gait is performed indoors on synthetic ice along with qualitative results of field deployment of the proprioceptive leader-follower and sidewinding gaits in extreme environments of icy and sandy terrains with mobility-stressing elements such as trenches, undulations, and steep slopes (up to 35 degrees). We present a set of lessons learned from field deployments with a summary of challenges and open research problems. Video: www. rohanthakker. in/eels-neo-autonomy. html

IROS Conference 2023 Conference Paper

Fast Point to Mesh Distance by Domain Voxelization

Geordan Gutow
Howie Choset

Computing the distance from a point to a triangle mesh is a key computational step in robotics pipelines such as registration and collision detection, with applications to path planning, SLAM, and RGB-D vision. Numerous techniques to accelerate this computation have been developed, many of which use a cheap pre-processing step to construct a hierarchical decomposition of the mesh. If the mesh is fixed and known ahead of time, there is an opportunity to conduct more expensive pre-computations to accelerate the subsequent distance queries. This work presents a voxelization approach, implemented on both CPU and GPU, to compute point to mesh distance that constructs for each voxel a near-minimal set of triangles that is guaranteed to include every triangle that is closest to at least one point in the voxel. Theoretical and numerical comparisons with six alternative distance algorithms demonstrate the speed advantages of the proposed method.

ICRA Conference 2023 Conference Paper

Learning Modular Robot Visual-motor Locomotion Policies

Julian Whitman
Howie Choset

Control policy learning for modular robot locomotion has previously been limited to proprioceptive feedback and flat terrain. This paper develops policies for modular systems with vision traversing more challenging environments. These modular robots can be reconfigured to form many different designs, where each design needs a controller to function. Though one could create a policy for individual designs and environments, such an approach is not scalable given the wide range of potential designs and environments. To address this challenge, we create a visual-motor policy that can generalize to both new designs and environments. The policy itself is modular, in that it is divided into components, each of which corresponds to a type of module (e. g. , a leg, wheel, or body). The policy components can be recombined during training to learn to control multiple designs. We develop a deep reinforcement learning algorithm where visual observations are input to a modular policy interacting with multiple environments at once. We apply this algorithm to train robots with combinations of legs and wheels, then demonstrate the policy controlling real robots climbing stairs and curbs.

ICML Conference 2023 Conference Paper

Learning Temporally AbstractWorld Models without Online Experimentation

Benjamin Freed
Siddarth Venkatraman
Guillaume Sartoretti
Jeff G. Schneider
Howie Choset

Agents that can build temporally abstract representations of their environment are better able to understand their world and make plans on extended time scales, with limited computational power and modeling capacity. However, existing methods for automatically learning temporally abstract world models usually require millions of online environmental interactions and incentivize agents to reach every accessible environmental state, which is infeasible for most real-world robots both in terms of data efficiency and hardware safety. In this paper, we present an approach for simultaneously learning sets of skills and temporally abstract, skill-conditioned world models purely from offline data, enabling agents to perform zero-shot online planning of skill sequences for new tasks. We show that our approach performs comparably to or better than a wide array of state-of-the-art offline RL algorithms on a number of simulated robotics locomotion and manipulation benchmarks, while offering a higher degree of adaptability to new goals. Finally, we show that our approach offers a much higher degree of robustness to perturbations in environmental dynamics, compared to policy-based methods.

IROS Conference 2023 Conference Paper

Multi-Agent Collective Construction Using 3D Decomposition

Akshaya Kesarimangalam Srinivasan
Shambhavi Singh
Geordan Gutow
Howie Choset
Bhaskar Vundurthy

Consider a Multi-Agent Collective Construction (MACC) problem that aims to generate a plan for fictitious cubic robots to build a three-dimensional structure comprised of cubic blocks. These cubic robots can carry one cubic block at a time; robots may move left, right, forwards, backward, or climb up or down one block. To construct structures taller than one cube, the robots must build supporting scaffolding made of blocks and remove the scaffolding once the structure is built. Prior works sought to create a planner that considered the structure as one monolithic assembly, which becomes intractable for larger workspaces and complex structures. To this end, we present a decomposition algorithm that breaks the structure into substructures that can be planned for independently. We use Mixed Integer Linear Programming (MILP) to plan for each of these substructures and then aggregate the solutions to construct the entire structure. Extensive testing on 200 randomly generated structures shows an order of magnitude improvement in the solution computation time compared to an MILP approach without decomposition. Finally, we leverage the independence between substructures to detect which substructures can be built in parallel.

IROS Conference 2023 Conference Paper

Multi-Agent Multi-Objective Ergodic Search Using Branch and Bound

Akshaya Kesarimangalam Srinivasan
Geordan Gutow
Zhongqiang Ren
Ian Abraham
Bhaskar Vundurthy
Howie Choset

Search and rescue applications often need multiple agents to complete a set of conflicting tasks. This paper studies a Multi-Agent Multi-Objective Ergodic Search (MA-MO-ES) approach to this problem where each objective or task is to cover a domain subject to an information map. The goal is to allocate coverage tasks to agents so that all maps are explored ergodically. The combinatorial nature of task allocation makes it computationally expensive to solve for optimal allocation using brute force. Apart from a large number of possible allocations, computing the cost of a task allocation is itself an expensive planning problem. To mitigate the computational challenge, we present a branch and bound-based algorithm with pruning techniques that reduce the number of allocations to be searched to find optimal coverage task allocation. We also present an approach to leverage the similarity between information maps to further reduce computation. Extensive testing on 147 randomly generated test cases shows an order of magnitude improvement in runtime compared to an exhaustive brute force approach.

ICRA Conference 2023 Conference Paper

Multi-Objective Ergodic Search for Dynamic Information Maps

Ananya Rao
Abigail Breitfeld
Alberto Candela
Benjamin Jensen
David Wettergreen
Howie Choset

Robotic explorers are essential tools for gathering information about regions that are inaccessible to humans. For applications like planetary exploration or search and rescue, robots use prior knowledge about the area to guide their search. Ergodic search methods find trajectories that effectively balance exploring unknown regions and exploiting prior information. In many search based problems, the robot must take into account multiple factors such as scientific information gain, risk, and energy, and update its belief about these dynamic objectives as they evolve over time. However, existing ergodic search methods either consider multiple static objectives or consider a single dynamic objective, but not multiple dynamic objectives. We address this gap in existing methods by presenting an algorithm called Dynamic Multi-Objective Ergodic Search (D-MO-ES) that efficiently plans an ergodic trajectory on multiple changing objectives. Our experiments show that our method requires up to nine times less compute time than a naïve approach with comparable coverage of each objective.

IROS Conference 2023 Conference Paper

Multi-Objective Sparse Sensing with Ergodic Optimization

Ananya Rao
Howie Choset

We consider a search problem where a robot has one or more types of sensors, each suited to detecting different types of targets or target information. Often, information in the form of a distribution of possible target locations, or locations of interest, may be available to guide the search. When multiple types of information exist, then a distribution for each type of information must also exist, thereby making the search problem that uses these distributions to guide the search a multi-objective one. In this paper, we consider a multi-objective search problem when the “cost” to use a sensor is limited. To this end, we leverage the ergodic metric, which drives agents to spend time in regions proportional to the expected amount of information there. We define the multi-objective sparse sensing ergodic (MO-SS-E) metric in order to optimize when and where each sensor measurement should be taken while planning trajectories that balance the multiple objectives. We observe that our approach maintains coverage performance as the number of samples taken considerably degrades. Further empirical results on different multi-agent problem setups demonstrate the applicability of our approach for both homogeneous and heterogeneous multi-agent teams.

IROS Conference 2023 Conference Paper

Real-Time Video Inpainting for RGB-D Pipeline Reconstruction

Luyuan Wang
Tina Tian
Xinzhi Yan
Fujun Ruan
G. Jaya Aadityaa
Howie Choset
Lu Li

This paper presents a Video Inpainting algorithm that enables monocular-camera-laser-based pipeline inspection robots to capture both color and 3D information using only one video stream. Conventional monocular-camera-laser inspection methods are limited to capture either 2D color images or 3D point clouds since the laser tends to overexpose the actual color of the scanning area. We propose a real-time Video Inpainting method to solve this problem with minimal hardware needs that can be easily integrated with conventional pipeline profiling robots. The algorithm is accelerated by two components: a lightweight network that directly predicts the complete optical flow and simplifies the algorithm pipeline, and the Polar coordinate transformation, which significantly reduces the image processing compexity. Real-world experiments demonstrate that our online algorithm has comparable or better color estimation accuracy against state-of-the-art offline algorithms, while is capable of running at 23 frames per second (FPS) on a laptop computer with a resolution of 1024 × 1024 pixels. In addition, we verify that this method can be used for video pre-processing for downstream tasks that require high-quality visual inputs, such as Simultaneously Localization and Mapping (SLAM). To the best of our knowledge, this is the first real-time Video Inpainting algorithm that can be used for in-pipe environments, serving as an important building block for highly compact RGB-D inspection sensors and robots for the pipeline industry.

ICRA Conference 2023 Conference Paper

Reslicing Ultrasound Images for Data Augmentation and Vessel Reconstruction

Cecilia G. Morales
Jason Yao
Tejas Rane
Robert Edman
Howie Choset
Artur Dubrawski

Robot-guided vascular access has the potential to deliver urgent medical care in situations where medical personnel are unavailable. However, this technique requires accurate and reliable segmentation of anatomical landmarks in the body. For the ultrasound imaging modality, obtaining large amounts of training data for a segmentation model is time-consuming and expensive. This paper introduces RESUS (RESlicing of UltraSound Images), a weak supervision data augmentation technique for ultrasound images based on slicing reconstructed 3D volumes from tracked 2D images. This technique allows us to generate views which cannot be easily obtained in vivo due to physical constraints of ultrasound imaging, and use these augmented ultrasound images to train a semantic segmentation model. We demonstrate that RESUS achieves statistically significant improvement over training with non-augmented images and highlight qualitative improvements through vessel reconstruction.

ICRA Conference 2023 Conference Paper

Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding

Zhongqiang Ren
Chaoran Zhang
Sivakumar Rathinam
Howie Choset

Multi-Agent Path Finding (MA-PF) computes a set of collision-free paths for multiple agents from their respective starting locations to destinations. This paper considers a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to be minimized. For example, an objective can be the sum or max of individual arrival times of the agents. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Pareto-optimal front that represents all possible trade-offs among the objectives of the teams. To solve MA-TC-PF, we propose two algorithms TC-CBS and TC-M*, which leverage the existing CBS and M* for conventional MA-PF. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front. We present numerical results for several types of MA-TC-PF problems.

SoCS Conference 2023 Conference Paper

Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding [Extended Abstract]

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

Multi-Agent Path Finding (MA-PF) finds collision-free paths for multiple agents from their respective start to goal locations. This paper investigates a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to minimize. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Pareto-optimal front that represents all possible trade-offs among the objectives of the teams. We show that the existing CBS and M* for MA-PF can be modified to solve MA-TC-PF, which is verified with tests. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front for MA-TC-PF.

ICRA Conference 2023 Conference Paper

Torque-Limited Manipulation Planning through Contact by Interleaving Graph Search and Trajectory Optimization

Ramkumar Natarajan
Garrison L. H. Johnston
Nabil Simaan
Maxim Likhachev
Howie Choset

Robots often have to perform manipulation tasks in close proximity to people (Fig 1). As such, it is desirable to use a robot arm that has limited joint torques so as to not injure the nearby person. Unfortunately, these limited torques then limit the payload capability of the arm. By using contact with the environment, robots can expand their reachable workspace that, otherwise, would be inaccessible due to exceeding actuator torque limits. We adapt our recently developed INSAT algorithm [1] to tackle the problem of torque-limited whole arm manipulation planning through contact. INSAT requires no prior over contact mode sequence and no initial template or seed for trajectory optimization. INSAT achieves this by interleaving graph search to explore the manipulator joint configuration space with incremental trajectory optimizations seeded by neighborhood solutions to find a dynamically feasible trajectory through contact. We demonstrate our results on a variety of manipulators and scenarios in simulation. We also experimentally show our planner exploiting robot-environment contact for the pick and place of a payload using a Kinova Gen3 robot. In comparison to the same trajectory running in free space, we experimentally show that the utilization of bracing contacts reduces the overall torque required to execute the trajectory.

IROS Conference 2023 Conference Paper

Toward Closed-Loop Additive Manufacturing: Paradigm Shift in Fabrication, Inspection, and Repair

Manpreet Singh
Fujun Ruan
Albert Xu
Yuchen Wu
Archit Rungta
Luyuan Wang
Kevin Song
Howie Choset

Increased usage of additive manufacturing (AM) in various industries has solidified its role as an advanced manufacturing technique. However, there is an inherent lack of reliability in AM processes, particularly common in extrusion or deposition-based methods due to the stochastic nature of ma-terial deposition. This necessitates an intelligent manufacturing solution to address the drawbacks of AM. Thus, we propose a novel layer-wise approach toward closed-loop AM, which is capable of in-situ monitoring and repairing geometric defects. In this paper, we present a system that uses a robotic AM experimental platform that mimics a conventional open-loop fabrication setup, which we augment into a closed-loop system using two add-ons: in-situ inspection subsystem and online process correction subsystem. The in-situ inspection subsystem collects 3D point cloud scans and compares them against a reference CAD model, categorizing geometric deviations as positive or negative defects. Then the subsequent online process correction subsystem uses a re-plan and/or repair strategy to address the positive and/or negative defects, respectively. To evaluate this idea, we conducted three experiments on parts with manually induced defects to investigate the system's ability to repair those parts, thereby reducing defects, improving part accuracy, and enhancing mechanical properties. Comparing the defective and repaired parts, we observe a reduction in defect percent by volume from 10. 7% to 1. 3%, an improvement in geometric tolerance from 3. 86% error to 0. 08% error, and an increase in the part's breaking load from 4. 77 kN to 6. 31 kN. These experiments prove that our layer-wise closed-loop additive manufacturing approach improves the quality, tolerance, and reliability of plastic 3D printed parts, with the potential to extend to other extrusion/deposition-based AM processes, or even subtractive manufacturing and hybrid manufacturing methods.

IROS Conference 2023 Conference Paper

Towards Automated Void Detection for Search and Rescue with 3D Perception

Ananya Bal
Ashutosh Gupta 0004
Pranav Goyal
David F. Merrick
Robin R. Murphy
Howie Choset

In a structural collapse, debris piles up in a chaotic and unstable manner, creating pockets and void spaces that are difficult to see or access. Often, these regions have the highest chances of concealing survivors and identifying such regions can increase the success of a search and rescue (SAR) operation while ensuring the safety of both survivors and rescue teams. In this paper, we present an approach for ex post facto void detection in rubble piles by using registered 3D point clouds reconstructed from aerial images captured at multiple times on the scene. We perform a temporal layering of these point clouds to capture the dynamic surface of the rubble pile from multiple days of the SAR operation and analyze this 3D structure to detect candidate regions corresponding to void spaces. The layering is achieved by a parallel 3D point cloud reconstruction of the scene using the COLMAP Structure from Motion pipeline. The void detection is achieved by applying multiple point filtering criteria in thin segments of the 3D point clouds of the rubble. We test our approach on aerial images collected from the Surfside Structural Collapse at Miami in June 2021. Our method achieves an improvement in registration compared to the use of standard point cloud registration methods on individual 3D reconstructions. Through our method, we see translation errors reduce by 82%. Additionally, our method detects 9 out of 10 void spaces that were observed by experts in the rubble.

IROS Conference 2023 Conference Paper

Unsupervised Deformable Ultrasound Image Registration and Its Application for Vessel Segmentation

Abhimanyu
Andrew L. Orekhov
Ananya Bal
John M. Galeotti
Howie Choset

This paper presents a deep-learning model for deformable registration of ultrasound images at online rates, which we call U-RAFT. As its name suggests, U-RAFT is based on RAFT, a convolutional neural network for estimating optical flow. U-RAFT, however, can be trained in an unsupervised manner and can generate synthetic images for training vessel segmentation models. We propose and compare the registration quality of different loss functions for training U-RAFT. We also show how our approach, together with a robot performing force-controlled scans, can be used to generate synthetic deformed images to significantly expand the size of a femoral vessel segmentation training dataset without the need for additional manual labeling. We validate our approach on both a silicone human tissue phantom as well as on in-vivo porcine images. We show that U-RAFT generates synthetic ultrasound images with 98% and 81% structural similarity index measure (SSIM) to the real ultrasound images for the phantom and porcine datasets, respectively. We also demonstrate that synthetic deformed images from U-RAFT can be used as a data augmentation technique for vessel segmentation models to improve intersection-over-union (IoU) segmentation performance.

IROS Conference 2023 Conference Paper

Visual-Inertial-Laser-Lidar (VILL) SLAM: Real-Time Dense RGB-D Mapping for Pipe Environments

Tina Tian
Luyuan Wang
Xinzhi Yan
Fujun Ruan
G. Jaya Aadityaa
Howie Choset
Lu Li

Robotic solutions for pipeline inspection promise enhancement of human labor by automating data acquisition for pipe condition assessments, which are vital for the early detection of pipe anomalies and the prevention of hazardous leakages and explosions. Through simultaneous localization and mapping (SLAM), colorized 3D reconstructions of the pipe's inner surface can be generated, providing a more comprehensive digital record of the pipes compared to conventional vision-only inspection. Designed for generic environments, most SLAM methods suffer limited accuracy and substantial accumulative drift in confined and featureless spaces such as pipelines, due to a lack of suitable sensor hardware and state estimation techniques. In this research, we present VILL-SLAM: a dense RGB-D SLAM algorithm that combines a monocular camera (V), an inertial sensor (I), a ring-shaped laser profiler (L), and a Lidar (L) into a compact sensor package optimized for in-pipe operations. By fusing complementary visual and depth information from the color camera, laser profiling, and Lidar measurement, our method overcomes the challenges of metric scale mapping in conventional SLAM methods, despite its monocular configuration. To further improve localization accuracy, we utilize the pipe geometry to formulate two unique optimization factors that effectively constrain odometer drift. To validate our method, we conducted real-world experiments in physical pipes, comparing the performance of our approach against other state-of-the-art algorithms. The proposed SLAM framework achieved 6. 6 times drift improvement with 0. 84% mean odometry drift over 22 meters and a mean pointwise 3D scanning error of 0. 88mm in 12-inch diameter pipes. This research represents a significant advancement in miniature in-pipe inspection, localization, and mapping sensing techniques. It has the potential to become a core enabling technology for the next generation of highly capable in-pipe robots, capable of reconstructing photo-realistic 3D pipe scans and providing disruptive pipe locating and georeferencing capabilities.

ICRA Conference 2022 Conference Paper

Autonomous Exploration Development Environment and the Planning Algorithms

Chao Cao
Hongbiao Zhu
Fan Yang 0092
Yukun Xia
Howie Choset
Jean Oh
Ji Zhang 0003

Autonomous Exploration Development Environment is an open-source repository released to facilitate development of high-level planning algorithms and integration of com-plete autonomous navigation systems. The repository contains representative simulation environment models, fundamental navigation modules, e. g. , local planner, terrain traversability analysis, waypoint following, and visualization tools. Together with two of our high-level planner releases - TARE planner for exploration and FAR planner for route planning, we detail usage of the three open-source repositories and share experiences in integration of autonomous navigation systems. We use DARPA Subterranean Challenge as a use case where the repositories together form the main navigation system of the CMU-OSU Team. In the end, we discuss a few potential use cases in extended applications.

ICRA Conference 2022 Conference Paper

Autonomous Ultrasound Scanning using Bayesian Optimization and Hybrid Force Control

Raghavv Goel
Abhimanyu
Kirtan Patel
John M. Galeotti
Howie Choset

Ultrasound scanning is an imaging technique that aids medical professionals in diagnostics and interventional procedures. However, a trained human-in-the-loop (HITL) with a radiologist is required to perform the scanning procedure. We seek to create a novel ultrasound system that can provide imaging in the absence of a trained radiologist, say for patients in the field who suffered injuries after a natural disaster. One challenge of automating ultrasound scanning involves finding the optimal area to scan and then performing the actual scan. This task requires simultaneously maintaining contact with the surface while moving along it to capture high quality images. In this work, we present an automated Robotic Ultrasound System (RUS) to tackle these challenges. Our approach introduces a Bayesian Optimization framework to guide the probe to multiple points on the unknown surface. Our proposed framework collects the ultrasound images as well as the pose information at every probed point to estimate regions with high vessel density (information map) and the surface contour. Based on the information map and the surface contour, an area of interest is selected for scanning. Furthermore, to scan the proposed region, a novel 6-axis hybrid force-position controller is presented to ensure acoustic coupling. Lastly, we provide experimental results on two different phantom models to corroborate our approach.

ICRA Conference 2022 Conference Paper

Design of a Biomimetic Tactile Sensor for Material Classification

Kevin Dai
Xinyu Wang
Allison M. Rojas
Evan Harber
Yu Tian
Nicholas Paiva
Joseph Gnehm
Evan Schindewolf

Tactile sensing typically involves active exploration of unknown surfaces and objects, making it especially effective at processing the characteristics of materials and textures. A key property extracted by human tactile perception in material classification is surface roughness, which relies on measuring vibratory signals using the multi-layered fingertip structure. Existing robotic systems lack tactile sensors that are able to provide high dynamic sensing ranges, perceive material properties, and maintain a low hardware cost. In this work, we introduce the reference design and fabrication procedure of a miniature and low-cost tactile sensor consisting of a biomimetic cutaneous structure, including the artificial fingerprint, dermis, epidermis, and an embedded magnet-sensor structure which serves as a mechanoreceptor for converting mechanical information to digital signals. The presented sensor is capable of detecting high-resolution magnetic field data through the Hall effect and creating high-dimensional time-frequency domain features for material texture classification. Additionally, we investigate the effects of different superficial sensor fingerprint patterns for classifying materials through both simulation and physical experimentation. After extracting time series and frequency domain features, we assess a k-nearest neighbors classifier for distinguishing between different materials. The results from our experiments show that our biomimetic tactile sensors with fingerprint ridges can classify materials with more than 7. 7% higher accuracy and lower variability than ridge-less sensors. These results, along with the low cost and customizability of our sensor, demonstrate high potential for lowering the barrier to entry for a wide array of robotic applications, including modelless tactile sensing for texture classification, material inspection, and object recognition.

SoCS Conference 2022 Conference Paper

Enhanced Multi-Objective A* Using Balanced Binary Search Trees

Zhongqiang Ren
Richard Zhan
Sivakumar Rathinam
Maxim Likhachev
Howie Choset

This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a "frontier" set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude.

ICRA Conference 2022 Conference Paper

Generalized Omega Turn Gait Enables Agile Limbless Robot Turning in Complex Environments

Tianyu Wang 0010
Baxi Chong
Yuelin Deng
Ruijie Fu
Howie Choset
Daniel I. Goldman

Reorientation (turning in plane) plays a critical role for all robots in any field application, especially those that in confined spaces. While important, reorientation remains a relatively unstudied problem for robots, including limbless mechanisms, often called snake robots. Instead of looking at snakes, we take inspiration from observations of the turning behavior of tiny nematode worms C. elegans. Our previous work presented an in-place and in-plane turning gait for limbless robots, called an omega turn, and prescribed it using a novel two-wave template [1]. In this work, we advance omega turn-inspired controllers in three aspects: 1) we use geometric methods to vary joint angle amplitudes and forward wave spatial frequency in our turning equation to establish a wide and precise amplitude modulation and frequency modulation on omega turn; 2) we use this new relationship to enable robots with fewer internal degrees of freedom (i. e. , fewer joints in the body) to achieve desirable performance, and 3) we apply compliant control methods to this relationship to handle unmodelled effects in the environment. We experimentally validate our approach on a limbless robot that the omega turn can produce effective and robust turning motion in various types of environments, such as granular media and rock pile.

ICRA Conference 2022 Conference Paper

Modular Robot Design Optimization with Generative Adversarial Networks

Jiaheng Hu
Julian Whitman
Matthew J. Travers
Howie Choset

Modular robots are made up of a set of components which can be configured and reconfigured to form customized robots for a wide range of tasks. Fully utilizing the flexibility of modular robots is challenging, as it requires the identification of optimal modular designs for each given task, often with limited computation and time. Previous works in design automation achieve efficient run-times by utilizing machine learning to create a one-to-one mapping from task to design. However, the problem of robot design is often multimodal, where multiple distinct designs can be similarly or equally good for a task. Alternative design solutions may be needed in the field, for instance, if a module in the optimal design fails and no replacement is available. This paper presents a novel method based on generative adversarial networks (GANs) that learns a one-to-many mapping from task to a distribution of designs. We apply our method to construct locomoting modular robots for terrains with varying obstacle heights and infill. We compare our method against the state-of-the-art, and find that our algorithm results in better solution quality, diversity, and alternatives for when the optimal design fails.

ICRA Conference 2022 Conference Paper

Multi-Agent Dynamic Ergodic Search with Low-Information Sensors

Howard Coffin
Ian Abraham
Guillaume Sartoretti
Tyler Dillstrom
Howie Choset

The long-term goal of this work is to enable agents with low-information sensors to perform tasks usually restricted to ones with more sophisticated, high-information sensing capabilities. Our approach is to regulate the motion of these low-information agents to obtain “high-information” results. As a first step, we consider a multi-agent system tasked with locating and tracking a moving target using only noisy binary sensors that measure the presence (or lack thereof) of a target in the sensor's field of view. To generate effective paths for these agents, we use ergodic trajectory optimization with a novel mutual information map that is fast to compute and can handle the discontinuous measurement models often associated with low-information sensing. We compare our approach with existing motion planning methods in multiple simulated experiments. Our experiments show that agents using our method outperform purely coverage-based approaches as well as naive ergodic approaches.

ICRA Conference 2022 Conference Paper

Periodic SLAM: Using Cyclic Constraints to Improve the Performance of Visual-Inertial SLAM on Legged Robots

Hans Kumar
J. Joe Payne
Matthew J. Travers
Aaron M. Johnson 0001
Howie Choset

Methods for state estimation that rely on visual information are challenging on legged robots due to rapid changes in the viewing angle of onboard cameras. In this work, we show that by leveraging structure in the way that the robot locomotes, the accuracy of visual-inertial SLAM in these challenging scenarios can be increased. We present a method that takes advantage of the underlying periodic predictability often present in the motion of legged robots to improve the performance of the feature tracking module within a visual-inertial SLAM system. Our method performs multi-session SLAM on a single robot, where each session is responsible for mapping during a distinct portion of the robot's gait cycle. Our method produces lower absolute trajectory error than several state-of-the-art methods for visual-inertial SLAM in both a simulated environment and on data collected on a quadrupedal robot executing dynamic gaits. On real-world bounding gaits, our median trajectory error was less than 35% of the error of the next best estimate provided by state-of-the-art methods.

IROS Conference 2022 Conference Paper

RGB-X Classification for Electronics Sorting

Abhimanyu
Tejas Zodage
Umesh Thillaivasan
Xinyue Lai
Rahul Chakwate
Javier Santillan
Emma Oti
Ming Zhao

Effectively disassembling and recovering materials from waste electrical and electronic equipment (WEEE) is a critical step in moving global supply chains from carbon-intensive, mined materials to recycled and renewable ones. Conventional recycling processes rely on shredding and sorting waste streams, but for WEEE, which is comprised of numerous dissimilar materials, we explore targeted disassembly of numerous objects for improved material recovery. Many WEEE objects share many key features and therefore can look quite similar, but their material composition and internal component layout can vary, and thus it is critical to have an accurate classifier for subsequent disassembly steps for accurate material separation and recovery. This work introduces RGB-X, a multi-modal image classification approach, that utilizes key features from external RGB images with those generated from X-ray images to accurately classify electronic objects. More specifically, this work develops Iterative Class Activation Mapping (iCAM), a novel network architecture that explicitly focuses on the finer-details in the multi-modal feature maps that are needed for accurate electronic object classification. In order to train a classifier, electronic objects lack large and well annotated X-ray datasets due to expense and need of expert guidance. To overcome this issue, we present a novel way of creating a synthetic dataset using domain randomization applied to the X-ray domain. The combined RGB-X approach gives us an accuracy of 98. 6% on 10 generations of modern smartphones, which is greater than their individual accuracies of 89. 1% (RGB) and 97. 9% (X-ray) independently. We provide experimental results 1 3 3 Experimental work done at Biorobotics Lab, Robotics Institute, Carnegie Mellon University to corroborate our results.

ICRA Conference 2021 Conference Paper

Autonomous Decentralized Shape-Based Navigation for Snake Robots in Dense Environments

Guillaume Sartoretti
Tianyu Wang 0010
Gabriel Chuang
Qingyang Li
Howie Choset

In this work, we focus on the autonomous navigation of snake robots in densely-cluttered environments, where collisions between the robot and obstacles are frequent, which could happen often in disaster scenarios, underground caves, or grassland/forest environments. This work takes the view that obstacles are not to be avoided, but rather exploited to support and direct the motion of the snake robot. We build upon a decentralized state-of-the-art compliant controller for serpenoid locomotion, and develop a bi-stable dynamical system that relies on inertial feedback to continuously steer the robot toward a desired direction. We experimentally show that this controller allows the robot to autonomously navigate dense environments by consistently locomoting along a given, global direction of travel in the world, which could be selected by a human operator or a higher level planner. We further equip the robot with an onboard vision system, allowing the robot to autonomously select its own direction of travel, based on the obstacle distribution ahead of its position (i. e. , enacting feedforward control). In those additional experiments on hardware, we show how such an exteroceptive sensor can allow the robot to steer before hitting obstacles and to preemptively avoid challenging regions where proprioception-only (i. e. , torque and inertial) feedback control would not suffice.

ICRA Conference 2021 Conference Paper

Equality Constrained Linear Optimal Control With Factor Graphs

Shuo Yang
Gerry Chen
Yetong Zhang
Howie Choset
Frank Dellaert

This paper presents a novel factor graph-based approach to solve the discrete-time finite-horizon Linear Quadratic Regulator problem subject to auxiliary linear equality constraints within and across time steps. We represent such optimal control problems using constrained factor graphs and optimize the factor graphs to obtain the optimal trajectory and the feedback control policies using the variable elimination algorithm with a modified Gram-Schmidt process. We prove that our approach has the same order of computational complexity as the state-of-the-art dynamic programming approach. Furthermore, current dynamic programming approaches can only handle equality constraints between variables at the same time step, but ours can handle equality constraints among any combination of variables at any time step while maintaining linear complexity with respect to trajectory length. Our approach can be used to efficiently generate trajectories and feedback control policies to achieve periodic motion or repetitive manipulation.

ICRA Conference 2021 Conference Paper

Exploring Large and Complex Environments Fast and Efficiently

Chao Cao
Hongbiao Zhu
Howie Choset
Ji Zhang 0003

This paper describes a novel framework for autonomous exploration in large and complex environments. We show that the framework is efficient as a result of its hierarchical structure, where at one level it maintains a sparse representation of the environment and at another level, a dense representation is used within a local planning horizon around the robot. The exploration path is computed at the two levels, coarsely at the global scale and finely around the robot. Such a framework produces detailed paths in the vicinity of the robot, while trades off data resolution far away from the robot for computational efficiency. In experiments, we evaluate our method with a real robot exploring large and complex indoor and outdoor environments. Results show that our method is twice as efficient in covering spaces while using less than one-fifth of processing in comparison to state-of-the-art methods.

IROS Conference 2021 Conference Paper

Geometric Motion Planning for a System on the Cylindrical Surface

Shuoqi Chen
Ruijie Fu
Ross L. Hatton
Howie Choset

Traditional geometric mechanics models used in locomotion analysis rely heavily on systems having symmetry in SE(2) (i. e. , the dynamics and constraints are invariant with respect to a system’s position and orientation) to simplify motion planning. As a result, the symmetry assumption prevents locomotion analysis on non-flat surfaces because the system dynamics may vary as a function of position and orientation. In this paper, we develop geometric motion planning strategies for a mobile system moving on a position space whose manifold structure is a cylinder: constant non-zero curvature in one dimension and zero curvature in another. To handle this non-flat position space, we adapt conventional geometric mechanics tools - in particular the system connection and the constraint curvature function - to depend on the system orientation. In addition, we introduce a novel constraint projection method to a variational gait optimizer and demonstrate how to design gaits that allow the example system to move on the cylinder with optimal efficiency.

IROS Conference 2021 Conference Paper

Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspace modeled as a graph, A*-based approaches have been widely investigated due to their guarantees on completeness and solution optimality, and have demonstrated their efficiency in many scenarios. However, almost all of these A*-based methods assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions (MAPF-AA) where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Numerical results are presented to corroborate the performance of LSS and the applicability of the proposed method is verified in the Robotarium, a remotely accessible swarm robotics research platform.

ICRA Conference 2021 Conference Paper

MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

In multi-agent applications such as surveillance and logistics, fleets of mobile agents are often expected to coordinate and safely visit a large number of goal locations as efficiently as possible. The multi-agent planning problem in these applications involves allocating and sequencing goals for each agent while simultaneously producing conflict-free paths for the agents. In this article, we introduce a new algorithm called MS* which computes an optimal solution for this multi-agent problem by fusing and advancing state of the art solvers for multi-agent path finding (MAPF) and multiple travelling salesman problem (mTSP). MS* leverages our prior subdimensional expansion approach for MAPF and embeds the mTSP solvers to optimally allocate and sequence goals for agents. Numerical results show that our new algorithm can solve the multi-agent problem with 20 agents and 50 goals in a minute of CPU time on a standard laptop.

ICRA Conference 2021 Conference Paper

Multi-objective Conflict-based Search for Multi-agent Path Finding

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. Naively applying existing multi-objective search algorithms to multi-agent path finding may prove to be inefficient as the size of the space of possible solutions, i. e. , the Pareto-optimal set, can grow exponentially with the number of agents (the dimension of the search space). This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality by leveraging prior Conflict-based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We prove that MO-CBS is able to compute the entire Pareto-optimal set. Our results show that MO-CBS can solve problem instances with hundreds of Pareto-optimal solutions which the standard multi-objective A* algorithms could not find within a bounded time.

ICRA Conference 2021 Conference Paper

Visual-Laser-Inertial SLAM Using a Compact 3D Scanner for Confined Space

Daqian Cheng
Haowen Shi
Albert Xu
Michael Schwerin
Michelle Crivella
Lu Li
Howie Choset

Three-dimensional reconstruction in confined spaces is important for the manufacturing of aircraft wings, inspection of narrow pipes, examination of turbine blades, etc. It is also challenging because confined spaces tend to lack a positioning infrastructure, and conventional sensors often cannot detect objects in close range. Therefore, such tasks require a sensor that is compact, operates in short-range, and able to localize itself. In this paper, we introduce a miniature and low-cost 3D scanning system including an active laser-stripe triangulation hardware, integrated inertial sensors, and a Simultaneous Localization and Mapping (SLAM) software tailored for the sensor. The proposed system is capable of reconstructing photo-realistic 3D point cloud in real-time in spite of its compact monocular configuration. To achieve this capability, we propose an approach to capture both color and geometry using alternating shutter-speed on a single camera. A novel SLAM method is proposed to accurately localize the sensor by fusing laser, camera, and inertial measurements. Evaluation of localization accuracy and comparison on reconstruction performance against a significantly larger commercial off-the-shelf sensor demonstrate the proposed system’s advantages in real-world applications.

AAAI Conference 2020 Conference Paper

Communication Learning via Backpropagation in Discrete Channels with Unknown Noise

Benjamin Freed
Guillaume Sartoretti
Jiaheng Hu
Howie Choset

This work focuses on multi-agent reinforcement learning (RL) with inter-agent communication, in which communication is differentiable and optimized through backpropagation. Such differentiable approaches tend to converge more quickly to higher-quality policies compared to techniques that treat communication as actions in a traditional RL framework. However, modern communication networks (e. g. , Wi- Fi or Bluetooth) rely on discrete communication channels, for which existing differentiable approaches that consider realvalued messages cannot be directly applied, or require biased gradient estimators. Some works have overcome this problem by treating the message space as an extension of the action space, and use standard RL to optimize message selection, but these methods tend to converge slower and to inferior policies. In this paper, we propose a stochastic message encoding/decoding procedure that makes a discrete communication channel mathematically equivalent to an analog channel with additive noise, through which gradients can be backpropagated. Additionally, we introduce an encryption step for use in noisy channels that forces channel noise to be message-independent, allowing us to compute unbiased derivative estimates even in the presence of unknown channel noise. To the best of our knowledge, this work presents the ﬁrst differentiable communication learning approach that can compute unbiased derivatives through channels with unknown noise. We demonstrate the effectiveness of our approach in two example multi-robot tasks: a path ﬁnding and a collaborative search problem. There, we show that our approach achieves learning speed and performance similar to differentiable communication learning with real-valued messages (i. e. , unlimited communication bandwidth), while naturally handling more realistic real-world communication constraints. Content Areas: Multi-Agent Communication, Reinforcement Learning.

ICRA Conference 2020 Conference Paper

Hierarchical Coverage Path Planning in Complex 3D Environments

Chao Cao
Ji Zhang 0003
Matthew J. Travers
Howie Choset

State-of-the-art coverage planning methods perform well in simple environments but take an ineffectively long time to converge to an optimal solution in complex three-dimensional (3D) environments. As more structures are present in the same volume of workspace, these methods slow down as they spend more time searching for all of the nooks and crannies concealed in three-dimensional spaces. This work presents a method for coverage planning that employs a multi-resolution hierarchical framework to solve the problem at two different levels, producing much higher efficiency than the state-of-the-art. First, a high-level algorithm separates the environment into multiple subspaces at different resolutions and computes an order of the subspaces for traversal. Second, a low-level sampling-based algorithm solves for paths within the subspaces for detailed coverage. In experiments, we evaluate our method using real-world datasets from complex three-dimensional scenes. Our method finds paths that are constantly shorter and converges at least ten times faster than the state-of-the-art. Further, we show results of a physical experiment where a lightweight UAV follows the paths to realize the coverage.

AAAI Conference 2020 Conference Paper

Modular Robot Design Synthesis with Deep Reinforcement Learning

Julian Whitman
Raunaq Bhirangi
Matthew Travers
Howie Choset

Modular robots hold the promise of versatility in that their components can be re-arranged to adapt the robot design to a task at deployment time. Even for the simplest designs, determining the optimal design is exponentially complex due to the number of permutations of ways the modules can be connected. Further, when selecting the design for a given task, there is an additional computational burden in evaluating the capability of each robot, e. g. , whether it can reach certain points in the workspace. This work uses deep reinforcement learning to create a search heuristic that allows us to efﬁciently search the space of modular serial manipulator designs. We show that our algorithm is more computationally efﬁcient in determining robot designs for given tasks in comparison to the current state-of-the-art.

IROS Conference 2020 Conference Paper

Optimizing coordinate choice for locomotion systems with toroidal shape spaces

Bo Lin 0006
Baxi Chong
Yasemin Ozkan Aydin
Enes Aydin
Howie Choset
Daniel I. Goldman
Greg Blekherman

In a geometric mechanics framework, the configuration space is decomposed into a shape space and a position space. The internal motion of the system is prescribed by a closed loop in the shape space, which causes net motion in the position space. If the shape space is a simply connected domain in an Euclidean space, then with an optimal choice of the body frame, the displacement in the position space is reasonably approximated by the surface integral of the height function, a functional relationship between the internal shape and position space variables. Our recent work has extended the scope of geometric methods from limbless undulatory system to those with legs; interestingly, the shape space for such systems has a torus structure. However, to the best of our knowledge, the optimal choice of the body frame on the torus shape space was not explored. In this paper, we develop a method to optimally choose the body frame on the torus which results in good approximation of displacement by the integral of the height function. We apply our methods to the centipede locomotion system and observe quantitative agreement of our prediction and experimental results.

IROS Conference 2020 Conference Paper

SeqSphereVLAD: Sequence Matching Enhanced Orientation-invariant Place Recognition

Peng Yin 0001
Fuying Wang
Anton Egorov
Jiafan Hou
Ji Zhang 0003
Howie Choset

Human beings and animals are capable of recognizing places from a previous journey when viewing them under different environmental conditions (e. g. , illuminations and weathers). This paper seeks to provide robots with a human-like place recognition ability using a new point cloud feature learning method. This is a challenging problem due to the difficulty of extracting invariant local descriptors from the same place under various orientation differences and dynamic obstacles. In this paper, we propose a novel lightweight 3D place recognition method, SeqSphereVLAD, which is capable of recognizing places from a previous trajectory regardless of the viewpoint and the temporary observation differences. The major contributions of our method lie in two modules: (1) the spherical convolution feature extraction module, which produces orientation-invariant local place descriptors, and (2) the coarse-to-fine sequence matching module, which ensures both accurate loop-closure detection and real-time performance. Despite the apparent simplicity, our proposed approach outperform the state-of-the-arts for place recognition under datasets that combine orientation and context differences. Compared with the arts, our method can achieve above 95% average recall for the best match with only 18% inference time of PointNet-based place recognition methods.

IROS Conference 2020 Conference Paper

Sparse Discrete Communication Learning for Multi-Agent Cooperation Through Backpropagation

Benjamin Freed
Rohan James
Guillaume Sartoretti
Howie Choset

Recent approaches to multi-agent reinforcement learning (MARL) with inter-agent communication have often overlooked important considerations of real-world communication networks, such as limits on bandwidth. In this paper, we propose an approach to learning sparse discrete communication through backpropagation in the context of MARL, in which agents are incentivized to communicate as little as possible while still achieving high reward. Building on top of our prior work on differentiable discrete communication learning, we develop a regularization-inspired message-length penalty term, that encourages agents to send shorter messages and avoid unnecessary communications. To this end, we introduce a variable-length message code that provides agents with a general means of modulating message length while keeping the overall learning objective differentiable. We present simulation results on a partially-observable robot navigation task, where we first show how our approach allows learning of sparse communication behavior while still solving the task. We finally demonstrate our approach can even learn an effective sparse communication behavior from demonstrations of an expert (potentially communication-free) policy.

IROS Conference 2020 Conference Paper

The Omega Turn: A Biologically-Inspired Turning Strategy for Elongated Limbless Robots

Tianyu Wang 0010
Baxi Chong
Kelimar Diaz
Julian Whitman
Hang Lu
Matthew J. Travers
Daniel I. Goldman
Howie Choset

Snake robots have the potential to locomote through tightly packed spaces, but turning effectively within unmodelled and unsensed environments remains challenging. Inspired by a behavior observed in the tiny nematode worm C. elegans, we propose a novel in-place turning gait for elongated limbless robots. To simplify the control of the robots' many internal degrees-of-freedom, we introduce a biologically-inspired template in which two co-planar traveling waves are superposed to produce an in-plane turning motion, the omega turn. The omega turn gait arises from modulating the wavelengths and amplitudes of the two traveling waves. We experimentally test the omega turn on a snake robot, and show that this turning gait outperforms previous turning gaits: it results in a larger angular displacement and a smaller area swept by the body over a gait cycle, allowing the robot to turn in highly confined spaces.

ICRA Conference 2019 Conference Paper

A Multi-modal Sensor Array for Safe Human-Robot Interaction and Mapping

Colette Abah
Andrew L. Orekhov
Garrison L. H. Johnston
Peng Yin 0001
Howie Choset
Nabil Simaan

In the future, human-robot interaction will include collaboration in close-quarters where the environment geometry is partially unknown. As a means for enabling such interaction, this paper presents a multi-modal sensor array capable of contact detection and localization, force sensing, proximity sensing, and mapping. The sensor array integrates Hall effect and time-of-flight (ToF) sensors in an I 2 C communication network. The design, fabrication, and characterization of the sensor array for a future in-situ collaborative continuum robot are presented. Possible perception benefits of the sensor array are demonstrated for accidental contact detection, mapping of the environment, selection of admissible zones for bracing, and constrained motion control of the end effector while maintaining a bracing constraint with an admissible rolling motion.

SoCS Conference 2019 Conference Paper

A-MHA*: Anytime Multi-Heuristic A

Ramkumar Natarajan
Muhammad Suhail Saleem
Sandip Aine
Maxim Likhachev
Howie Choset

Designing good heuristic functions for graph search requires adequate domain knowledge. It is often easy to design heuristics that perform well and correlate with the underlying true cost-to-go values in certain parts of the search space but these may not be admissible throughout the domain thereby affecting the optimality guarantees of the search. Bounded suboptimal search using several of such partially good but inadmissible heuristics was developed in Multi-Heuristic A* (MHA*). Although MHA* leverages multiple inadmissible heuristics to potentially generate a faster suboptimal solution, the original version does not improve the solution over time. It is an one shot algorithm that requires careful setting of inflation factors to obtain a desired one time solution. In this work, we tackle this issue by extending MHA* to an anytime version that finds a feasible suboptimal solution quickly and continually improve it until time runs out. Our work is inspired from the Anytime Repairing A* (ARA*) algorithm. We prove that our precise adaptation of ARA* concepts in the MHA* framework preserves the original suboptimal and completeness guarantees and enhances MHA* to perform in an anytime fashion. Furthermore, we report the performance of A-MHA* in 3-D path planning domain and sliding tiles puzzle and compare against MHA* and other anytime algorithms.

ICRA Conference 2019 Conference Paper

Workspace CPG with Body Pose Control for Stable, Directed Vision during Omnidirectional Locomotion

Samuel Shaw
Guillaume Sartoretti
Jake Olkin
William Paivine
Howie Choset

In this paper, we focus on the problem of directing the gaze of a vision system mounted to the body of a high-degree-of-freedom (DOF) legged robot for active perception deployments. In particular, we consider the case where the vision system is rigidly attached to the robot's body (i. e. , without any additional DOF between the vision system and robot body) and show how the supernumerary DOFs of the robot can be leveraged to allow independent locomotion and gaze control. Specifically, we augment a workspace central pattern generator (CPG) with omnidirectional capabilities by coupling it with a body pose control mechanism. We leverage the smoothing nature of the CPG framework to allow online adaptation of relevant locomotion parameters, and obtain a stable mid-level controller that translates desired gaze orientation and body velocity directly into joint angles. We validate our approach on an 18-DOF hexapod robot, in a series of indoor and outdoor trials, where the robot inspects an environmental feature or follows a pre-planned path relative to a visually-tracked landmark, demonstrating simultaneous locomotion and directed vision.

ICRA Conference 2018 Conference Paper

Central Pattern Generator With Inertial Feedback for Stable Locomotion and Climbing in Unstructured Terrain

Guillaume Sartoretti
Samuel Shaw
Katie Lam
Naixin Fan
Matthew J. Travers
Howie Choset

Inspired by the locomotor nervous system of vertebrates, central pattern generator (CPG) models can be used to design gaits for articulated robots, such as crawling, swimming or legged robots. Incorporating sensory feedback for gait adaptation in these models can improve the locomotive performance of such robots in challenging terrain. However, many CPG models to date have been developed exclusively for open-loop gait generation for traversing level terrain. In this paper, we present a novel approach for incorporating inertial feedback into the CPG framework for the control of body posture during legged locomotion on steep, unstructured terrain. That is, we adapt the limit cycle of each leg of the robot with time to simultaneously produce locomotion and body posture control. We experimentally validate our approach on a hexapod robot, locomoting in a variety of steep, challenging terrains (grass, rocky slide, stairs). We show how our approach can be used to level the robot's body, allowing it to locomote at a relatively constant speed, even as terrain steepness and complexity prevents the use of an open-loop control strategy.

ICRA Conference 2018 Conference Paper

Distributed Learning for the Decentralized Control of Articulated Mobile Robots

Guillaume Sartoretti
Yunfei Shi
William Paivine
Matthew J. Travers
Howie Choset

Decentralized control architectures, such as those conventionally defined by central pattern generators, independently coordinate spatially distributed portions of articulated bodies to achieve system-level objectives. State of the art distributed algorithms for reinforcement learning employ a different but conceptually related idea; independent agents simultaneously coordinating their own behaviors in parallel environments while asynchronously updating the policy of a system-or, rather, meta-level agent. This work, to the best of the authors' knowledge, is the first to explicitly explore the potential relationship between the underlying concepts in homogeneous decentralized control for articulated locomotion and distributed learning. We present an approach that leverages the structure of the asynchronous advantage actor-critic (A3C) algorithm to provide a natural framework for learning decentralized control policies on a single platform. Our primary contribution shows an individual agent in the A3C algorithm can be defined by an independently controlled portion of the robot's body, thus enabling distributed learning on a single platform for efficient hardware implementation. To this end, we show how the system is trained offline using hardware experiments implementing an autonomous decentralized compliant control framework. Our experimental results show that the trained agent outperforms the compliant control baseline by more than 40% in terms of steady progression through a series of randomized, highly cluttered evaluation environments.

ICRA Conference 2018 Conference Paper

Proprioceptive-Inertial Autonomous Locomotion for Articulated Robots

Francesco Ruscelli
Guillaume Sartoretti
Junyu Nan
Zhixin Feng
Matthew J. Travers
Howie Choset

Inspired by the ability of animals to rely on proprioception and vestibular feedback to adapt their gait, we propose a modular framework for autonomous locomotion that relies on force sensing and inertial information. A first controller exploits anti-compliance, a new application of positive force feedback, to quickly react against obstacles upon impact. We hypothesize that, in situations where a robot experiences occasional impacts with the environment, anti-compliance can help negotiate unknown obstacles, similar to biological systems where positive feedback enables fast responses to external stimuli. A novel parallel controller, based on a bi-stable dynamical system, continuously adjusts the robot's direction of locomotion, and reverts it in reaction to major swerves. We present experimental results, demonstrating how our framework allows a snake robot to autonomously locomote through a row of unevenly-spaced obstacles. Finally, we extend our proprioceptive controller to legged locomotion, showing how a hexaprint robot can adapt its motion to climb over obstacles.

SoCS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding Solvers

Liron Cohen 0002
Glenn Wagner
David M. Chan
Howie Choset
Nathan R. Sturtevant
Sven Koenig
T. K. Satish Kumar

Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rate for a given runtime limit. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* with highways and CBS-CL.

AAMAS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results

Liron Cohen
Sven Koenig
T. K. Satish Kumar
Glenn Wagner
Howie Choset
David Chan
Nathan Sturtevant

Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.

IROS Conference 2018 Conference Paper

Stabilize an Unsupervised Feature Learning for LiDAR-based Place Recognition

Peng Yin 0001
Lingyun Xu
Zhe Liu 0022
Lu Li
Hadi Salman
Yuqing He
Weiliang Xu 0001
Hesheng Wang 0001

Place recognition is one of the major challenges for the LiDAR-based effective localization and mapping task. Traditional methods are usually relying on geometry matching to achieve place recognition, where a global geometry map need to be restored. In this paper, we accomplish the place recognition task based on an end-to-end feature learning framework with the LiDAR inputs. This method consists of two core modules, a dynamic octree mapping module that generates local 2D maps with the consideration of the robot's motion; and an unsupervised place feature learning module which is an improved adversarial feature learning network with additional assistance for the long-term place recognition requirement. More specially, in place feature learning, we present an additional Generative Adversarial Network with a designed Conditional Entropy Reduction module to stabilize the feature learning process in an unsupervised manner. We evaluate the proposed method on the Kitti dataset and North Campus Long-Term LiDAR dataset. Experimental results show that the proposed method outperforms state-of-the-art in place recognition tasks under long-term applications. What's more, the feature size and inference efficiency in the proposed method are applicable in real-time performance on practical robotic platforms.

ICRA Conference 2018 Conference Paper

Trajectory-Optimized Sensing for Active Search of Tissue Abnormalities in Robotic Surgery

Hadi Salman
Elif Ayvali
Rangaprasad Arun Srivatsan
Yifei Ma
Nico Zevallos
Rashid Yasin
Long Wang 0007
Nabil Simaan

In this work, we develop an approach for guiding robots to automatically localize and find the shapes of tumors and other stiff inclusions present in the anatomy. Our approach uses Gaussian processes to model the stiffness distribution and active learning to direct the palpation path of the robot. The palpation paths are chosen such that they maximize an acquisition function provided by an active learning algorithm. Our approach provides the flexibility to avoid obstacles in the robot's path, incorporate uncertainties in robot position and sensor measurements, include prior information about location of stiff inclusions while respecting the robot-kinematics. To the best of our knowledge this is the first work in literature that considers all the above conditions while localizing tumors. The proposed framework is evaluated via simulation and experimentation on three different robot platforms: 6-DoF industrial arm, da Vinci Research Kit (dVRK), and the Insertable Robotic Effector Platform (IREP). Results show that our approach can accurately estimate the locations and boundaries of the stiff inclusions while reducing exploration time.

IROS Conference 2017 Conference Paper

Deformed state lattice planning

Zhongqiang Ren
Chaohui Gong
Howie Choset

Search-based planning that uses a state lattice has been successfully applied in many applications but its utility is limited when confronted with complex problems represented by a lattice with many nodes and edges with high branching factor. However, in many seemingly complex problems, proper “form-fitting” can reduce the number of nodes and edges needed to represent the problems, provides a concise state lattice and therefore simplifies the computation. This paper proposes a planning framework which strikes to identify concise representations of problems, creates such “form-fitting” state lattice on which a more concise search can take place. In a sense, we take a conventional state lattice and map it onto a deformed space, and then the motion primitives and heuristics follow. Since the contribution of the paper is not the search approach but rather the means by which the lattice is deformed, any search-based planner can then be easily changed to a corresponding deformed version with no increase in time complexity. This paper demonstrate the benifits of the approach which includes 1) planned path can be followed with few changes in motion primitives and thus can provide global smoothness of planned path; 2) fewer states are expanded and thus shorter time to search solution in state space is required, and 3) fewer states are expanded and thus less memory is required to save the state lattice. We demonstrate the benefit of the proposed approach in illustrative toy examples, as well as robot experiments.

IROS Conference 2017 Conference Paper

Development of an inexpensive tri-axial force sensor for minimally invasive surgery

Lu Li
Bocheng Yu
Chen Yang
Prasad Vagdargi
Rangaprasad Arun Srivatsan
Howie Choset

This work presents the design and evaluation of a low-cost tri-axial force sensor, that has been developed to regain the sense of touch in minimally invasive surgeries (MIS). The force sensor uses an array of force sensitive resistors (FSR) with a mechanically pre-loaded structure to perform the force sensing. The sensor has a built-in signal conditioning circuitry to provide on-board power regulation, programmable signal amplification and analog to digital conversion. The sensor is inexpensive and highly sensitive to low-amplitude force, critical in surgical applications. We validate the efficacy of the sensor with two surgical applications - robotic palpation for stiffness mapping and obstacle avoidance for a highly articulated robotic probe (HARP). The results show that the sensor is capable of accurately detecting the stiff inclusions embedded in the tissues as well as detecting obstacles and helping HARP safely navigate around them.

IROS Conference 2017 Conference Paper

Ergodic coverage in constrained environments using stochastic trajectory optimization

Elif Ayvali
Hadi Salman
Howie Choset

In search and surveillance applications in robotics, it is intuitive to spatially distribute robot trajectories with respect to the probability of locating targets in the domain. Ergodic coverage is one such approach to trajectory planning in which a robot is directed such that the percentage of time spent in a region is in proportion to the probability of locating targets in that region. In this work, we extend the ergodic coverage algorithm to robots operating in constrained environments and present a formulation that can capture sensor footprint and avoid obstacles and restricted areas in the domain. We demonstrate that our formulation easily extends to coordination of multiple robots equipped with different sensing capabilities to perform ergodic coverage of a domain.

IROS Conference 2017 Conference Paper

Generating gaits for simultaneous locomotion and manipulation

Julian Whitman
Shuang Su
Stelian Coros
Alex Ansari
Howie Choset

Modular robots can be rapidly reconfigured into customized articulated legged morphologies capable of mobile manipulation and inspection. However, current gait generation methods do not keep pace with the speed of physical reconfiguration. This work focuses on quickly creating gaits for modular legged robots. We build on a recent method that uses trajectory optimization to design quasi-static gaits given only robot geometry and foot contact patterns. We develop methods to automatically generate contact patterns for new gaits and transitions between them. We show the utility of these methods applied to robots with many limbs, such that limbs can be fluidly reassigned to locomotion, manipulation, or inspection tasks, or to adapt gaits to hardware failures online. We demonstrate gait and transition generation with our modular hexapod and dodecapod robots. The robots switch between gaits that use all limbs for locomotion and those that leave some limbs free to pick up objects or position a camera.

ICAPS Conference 2017 Conference Paper

Multi-Agent Ergodic Coverage with Obstacle Avoidance

Hadi Salman
Elif Ayvali
Howie Choset

Autonomous exploration and search have important applications in robotics. One interesting application is cooperative control of mobile robotic/sensor networks to achieve uniform coverage of a domain. Ergodic coverage is one solution for this problem in which control laws for the agents are derived so that the agents uniformly cover a target area while maintaining coordination with each other. Prior approaches have assumed the target regions contain no obstacles. In this work, we tackle the problem of static and dynamic obstacle avoidance while maintaining an ergodic coverage goal. We pursue a vector-field-based obstacle avoidance approach and define control laws for idealized kinematic and dynamic systems that avoid static and dynamic obstacles while maintaining ergodicity. We demonstrate this obstacle avoidance methodology via numerical simulation and show how ergodicity is maintained.

ICAPS Conference 2017 Conference Paper

Path Planning for Multiple Agents under Uncertainty

Glenn Wagner
Howie Choset

Multi-agent systems in cluttered environments require path planning that not only prevents collisions with static obstacles, but also safely coordinates the motion of many agents. The challenge of multi-agent path finding becomes even more difficult when the agents experience uncertainty in their pose. In this work, we develop a multi-agent path planner that considers uncertainty, called uncertainty M* (UM*), which is based on a prior multi-agent path approach called M*. UM* plans a path through the belief space for each individual agent and then uses a strategy similar to M* that coordinates only agents that are “likely” to collide. This approach has the same scalability advantages as M*. We then introduce an extension called Permuted UM* (PUM*) that uses randomized restarts to enhance performance. We finish by presenting a belief space representation appropriate for multi-agent path planning with uncertainty and validate the performance of UM* and PUM* in simulation and mixed-reality experiments.

ICRA Conference 2016 Conference Paper

Complementary model update: A method for simultaneous registration and stiffness mapping in flexible environments

Rangaprasad Arun Srivatsan
Elif Ayvali
Long Wang 0007
Rajarshi Roy 0005
Nabil Simaan
Howie Choset

Registering a surgical tool to an a priori model of the environment is an important first step in computer-aided surgery. In this paper we present an approach for simultaneous registration and stiffness mapping using blind exploration of flexible environments. During contact-based exploration of flexible environments, the physical interaction with the environment can induce local deformation, leading to erroneous registration if not accounted for. To overcome this issue, a new registration method called complementary model update (CMU), is introduced. By incorporating measurements of the contact force, and contact location, we minimize a unique objective function to cancel out the effect of local deformation. We are thus able to acquire the necessary registration parameters using both geometry and stiffness information. The proposed CMU method is evaluated in simulation and using experimental data obtained by probing silicone models and an ex vivo organ.

IROS Conference 2016 Conference Paper

Multirobot sequential composition

Glenn Wagner
Howie Choset
Avinash Siravuru

Conventional path planning algorithms compute a single path through the configuration space. There is no guarantee that a physical robot will be able to track the trajectory while avoiding collisions, particularly in the presence of environmental perturbations and errors in the process model. Sequential composition combines planning and control by computing a sequence of controllers to execute rather than a single trajectory, offering greater safety guarantees. In this paper, we apply sequential composition to multirobot systems in a scalable fashion using M*, an advanced multirobot path planning algorithm. Controllers will vary in size and geometry, and thus take different amounts of time to execute. To handle these differences, we introduce the time augmented joint prepares graph and the approximate time augmented joint prepares graph which simplifies implementation by discretizing time. We validate our approach in a mixed reality test framework.

IROS Conference 2016 Conference Paper

Optimal control for geometric motion planning of a robot diver

Roberto Shu
Avinash Siravuru
Akshara Rai
Tony Dear
Koushil Sreenath
Howie Choset

Inertial reorientation of airborne articulated bodies has been an active area of research in the robotics community, as this behavior can help guide dynamic robots to a safe landing with minimal damage. The main objective of this work is emulating the aggressive and large angle correction maneuvers, like somersaults, that are performed by human divers. To this end, a planar three link robot, called DiverBot, is proposed. By considering a gravity-free scenario, a local connection is obtained between joint angles and the body orientation, resulting in a reduction in the system dynamics. An optimal control policy applied on this reduced configuration space yielded diving maneuvers that are dynamically feasible. Numerical results show that the DiverBot can execute one somersault without drift and multiple somersaults with minimal drift.

SoCS Conference 2016 Conference Paper

Recursive Constraint Manifold Subsearch for Multirobot Path Planning with Cooperative Tasks

Péter Karkus
Glenn Wagner
Howie Choset

The Cooperative Path Planning (CPP) problem seeks to determine a path for a group of robots which form temporary teams to perform tasks. The multi-scale effects of simultaneously coordinating many robots distributed across the workspace while also tightly coordinating the members of teams increases the difficulty of planning. Previous research produced the Constraint Manifold Subsearch (CMS) algorithm that can find minimal length paths to the CPP problem. However, CMS as currently formulated cannot handle more general cost functions, such as minimizing energy expenditure, and cannot handle task schedules that require multiple input teams to merge to form a set of multiple output teams. Furthermore, as CMS must couple planning for all interacting teams, it does not scale well to very large environments. In this paper, we rederive the CMS algorithm using a task graph to reason about inter-team dependencies, allowing the use of more general cost functions and task schedules. We then introduce the recursive CMS (rCMS) algorithm that exploits the reformulation to split the CPP into independent subproblems, significantly reducing computational complexity. Simulation studies show that rCMS can solve substantially larger problems than CMS.

ICRA Conference 2016 Conference Paper

Using Bayesian optimization to guide probing of a flexible environment for simultaneous registration and stiffness mapping

Elif Ayvali
Rangaprasad Arun Srivatsan
Long Wang 0007
Rajarshi Roy 0005
Nabil Simaan
Howie Choset

One of the goals of computer-aided surgery is to register intraoperative data to preoperative model of the anatomy, and hence add complementary information that can facilitate the task of surgical navigation. In this context, mechanical palpation can reveal critical anatomical features such as arteries and cancerous lumps which are stiffer than the surrounding tissue. This work uses position and force measurements obtained during mechanical palpation for registration and stiffness mapping. Prior approaches, including our own, exhaustively palpated the entire organ to achieve this goal. To overcome the costly palpation of the entire organ, a Bayesian optimization framework is introduced to guide the end effector to palpate stiff regions while simultaneously updating the registration of the end effector to an a priori geometric model of the organ, hence enabling the fusion of intraoperative data into the a priori model obtained through imaging. This new framework uses Gaussian processes to model the stiffness distribution and Bayesian optimization to direct where to sample next for maximum information gain. The proposed method was evaluated with experimental data obtained using a Cartesian robot interacting with a silicone organ model and an ex vivo porcine liver.

ICRA Conference 2015 Conference Paper

Constraint Manifold Subsearch for multirobot path planning with cooperative tasks

Glenn Wagner
Jae-il Kim
Konrad Urban
Howie Choset

The cooperative path planning problem seeks to determine a path for a group of robots which form temporary teams to perform tasks that require multiple robots. The multi-scale effects of simultaneously coordinating many robots distributed across the workspace while also tightly coordinating robots in cooperative teams increases the difficulty of planning. This paper describes a new approach to cooperative path planning called Constraint Manifold Subsearch (CMS). CMS builds upon M*, a high performance multirobot path planning algorithm, by modifying the search space to restrict teams of robots performing a task to the constraint manifold of the task. CMS can find optimal solutions to the cooperative path planning problem, or near optimal solutions to problems involving large numbers of robots.

ICRA Conference 2015 Conference Paper

Gaussian reconstruction of swarm behavior from partial data

Glenn Wagner
Howie Choset

Swarms consist of large numbers of individual agents that generally maintain no fixed relative positions, which makes describing the behavior of the swarm as a whole difficult. Furthermore, the high number of agents leads to frequent occlusions that prevent observations of the entire swarm. In this paper, we represent the behavior of swarms using velocity fields, yielding a description which is invariant to the number of agents in a swarm, and the position, orientation, and scale of the swarm. The velocity field representation allows the behavior of swarms to be modeled as a Gaussian distribution. We demonstrate that this Gaussian model can be used to reconstruct the behavior of the swarm as a whole from partial observations.

ICRA Conference 2015 Conference Paper

Limbless locomotors that turn in place

Chaohui Gong
Matthew J. Travers
Henry C. Astley
Daniel I. Goldman
Howie Choset

Our research group has started a collaboration that analyzes data collected from biological snakes to provide insight on how to better program snake robots. Most data collected on biological snakes views the snakes from above and thus can only detect motion in the horizontal plane. However, both our robots and biological snakes are capable of generating motions both in the horizontal and vertical planes. Vertical waves naturally play a major role in limbless locomotion in that they simultaneously provide thrust motion and make-and-break contact between the mechanism and environment. Analysis on the data, collected from sidewinder rattle snakes, revealed that disparate modes of locomotion emerged from different contact patterns. We conclude that the same horizontal undulation can cause dramatically different motions for both the biological and robotic snakes depending upon the choice of contacts. With this knowledge, we introduce contact scheduling, a technique that plans positions of contacts along the body to design gaits for snake robots. Contact scheduling results in a novel turning gait, which can reorient a snake robot more than 90 degrees in one gait cycle.

ICRA Conference 2015 Conference Paper

Locomotive reduction for snake robots

Xuesu Xiao
Ellen A. Cappo
Weikun Zhen
Jin Dai
Ke Sun 0002
Chaohui Gong
Matthew J. Travers
Howie Choset

Limbless locomotion, evidenced by both biological and robotic snakes, capitalizes on these systems' redundant degrees of freedom to negotiate complicated environments. While the versatility of locomotion methods provided by a snake-like form is of great advantage, the difficulties in both representing the high dimensional workspace configuration and implementing the desired translations and orientations makes difficult further development of autonomous behaviors for snake robots. Based on a previously defined average body frame and set of motion primitives, this work proposes locomotive reduction, a simplifying methodology which reduces the complexity of controlling a redundant snake robot to that of navigating a differential-drive vehicle. We verify this technique by controlling a 16-DOF snake robot using locomotive reduction combined with a visual tracking system. The simplicity resulting from the proposed locomotive reduction method allows users to apply established autonomous navigation techniques previously developed for differential-drive cars to snake robots. Best of all, locomotive reduction preserves the advantages of a snake robot's ability to perform a variety of locomotion modes when facing complicated mobility challenges.

ICRA Conference 2015 Conference Paper

Mobile manufacturing of large structures

David A. Bourne
Howie Choset
Humphrey Hu
George Kantor
Chris Niessl
Zachary B. Rubinstein
Reid G. Simmons
Stephen F. Smith

Assembly of large structures requires large fixtures, often referred to as monuments. Their cost and massive size limit flexibility and scalability of the manufacturing process. Numerous small mobile robots can replace these large structures and, therefore, replicate the efficiency of the assembly line with far more flexibility. An assembly line made up of mobile manipulators can easily and rapidly be reconfigured to support scalability and a varied product mix, while allowing for near optimal resource assignment. The challenge to using small robots in place of monuments is making their joint behavior precise enough to accomplish the task and efficient enough to execute subtasks in a reasonable period of time. In this paper, we describe a set of techniques that we combine to achieve the necessary precision and overall efficiency to build a large structure. We describe and demonstrate these techniques in the context of a testbed we implemented for assembling a wing ladder.

ICRA Conference 2015 Conference Paper

Modeling rolling gaits of a snake robot

Weikun Zhen
Chaohui Gong
Howie Choset

Successful deployment of a snake robot in search and rescue tasks requires the capability of generating controls which can adapt to unknown environments in real-time. However, available motion generation techniques can be computationally expensive and lack the ability to adapt to the surroundings. This work considers modeling the rolling motion of a snake robot by applying the Bellows model with computation reduction techniques. One benefit of this is that controllers are defined with physically meaningful parameters, which in turn allows for higher level control of the robot. Another benefit is that it allows controllers to be defined by “composing shapes”, which enables developing controllers that can adapt to the surroundings. Using shape composition, we implemented a novel gait, named rolling hump, which forms a contour-fitting hump to negotiate obstacles. The efficacy of a snake robot climbing over obstacles by using the rolling hump is experimentally evaluated. An autonomous control strategy is presented and realized in simulation.

ICRA Conference 2015 Conference Paper

Robot-inspired biology: The compound-wave control template

Jin Dai
Matthew J. Travers
Tony Dear
Chaohui Gong
Henry C. Astley
Daniel I. Goldman
Howie Choset

Biologically inspired robots perform many interesting and useful behaviors, but to effectively emulate their biological counterparts, robots often need to possess many degrees of freedom, complicating their mechanical design and making it difficult to apply standard control and motion planning strategies. To address this complexity, the robotics community has derived low-dimensional parameter-based controllers that naturally coordinate many degrees of freedom such as the serpenoid curves used to control snake robots. Controllers utilizing this parameterization for snake robots have been able to induce behaviors similar to that of the robots' biological counterparts. A similar concept, called a control template, is used in the study of animal movements. However, much of the prior work on control templates has been limited to in-plane motion. In this work, we extend the usage of control templates to three dimensions to both better model and understand biology, as well as to help us gain better intuition into how we can use pre-existing control paradigms to create new behaviors for biologically inspired robots.

ICRA Conference 2015 Conference Paper

Snakeboard motion planning with viscous friction and skidding

Tony Dear
Scott David Kelly
Matthew J. Travers
Howie Choset

The snakeboard is a well-studied example for mechanical systems analysis, largely because of its simultaneous richness in behavior and simplicity in design. However, few snakeboard models incorporate dissipative friction in the traveling direction and skidding as a violation of the rigid nonholonomic constraints. In this paper we investigate these effects on trajectory planning by evaluating a previously proposed friction model as well as a novel skidding model based on the addition of Rayleigh dissipation functions. We show how these additions change the usual behavior of gaits in the forward planning problem, and incorporate the changes into the solutions of the inverse planning problem by utilizing body coordinates along with a curvature parameterization for trajectories.

AIJ Journal 2015 Journal Article

Subdimensional expansion for multirobot path planning

Glenn Wagner
Howie Choset

Planning optimal paths for large numbers of robots is computationally expensive. In this paper, we introduce a new framework for multirobot path planning called subdimensional expansion, which initially plans for each robot individually, and then coordinates motion among the robots as needed. More specifically, subdimensional expansion initially creates a one-dimensional search space embedded in the joint configuration space of the multirobot system. When the search space is found to be blocked during planning by a robot–robot collision, the dimensionality of the search space is locally increased to ensure that an alternative path can be found. As a result, robots are only coordinated when necessary, which reduces the computational cost of finding a path. We present the M ⁎ algorithm, an implementation of subdimensional expansion that adapts the A ⁎ planner to perform efficient multirobot planning. M ⁎ is proven to be complete and to find minimal cost paths. Simulation results are presented that show that M ⁎ outperforms existing optimal multirobot path planning algorithms.

ICRA Conference 2015 Conference Paper

Use of the nonlinear observability rank condition for improved parametric estimation

Matthew J. Travers
Howie Choset

The correct way to design controllers for dynamic robots is still very much an open question. This is in a large part due to the complexity and uncertainty in modeling their nonlinear dynamics. In this work, we focus on deriving concise dynamic expressions for a particular class of robots that can be used to better reduce uncertainty with respect to unknown parameters in realtime. We accomplish this by using an extended Kalman filtering framework in conjunction with an online controller that continuously maximizes a local measure of nonlinear observability. The main novel contribution of this work is that we directly use the nonlinear observability rank condition to derive the measure of observability at each time step. We are able to make this extension in part by focusing on serial-chain systems and exploiting the geometric structure in their dynamic models. In particular, we derive concise, closed-form and exact analytical representations for the forward dynamics, linearization, and nonlinear observability rank condition of a fixed-base serial manipulator with actively controlled elastic joints. An example is presented in which the spring constants and damping coefficients for a series-elastic actuated manipulator are estimated using the online observability maximizing techniques we derive.

IROS Conference 2014 Conference Paper

Design and architecture of a series elastic snake robot

David Rollinson
Yigit Bilgen
Ben Brown
Florian Enner
Steven Ford
Curtis Layton
Justine Rembisz
Michael Schwerin

This paper details the design and architecture of a series elastic actuated snake robot, the SEA Snake. The robot consists of a series chain of 1-DOF modules that are capable of torque, velocity and position control. Additionally, each module includes a high-speed Ethernet communications bus, internal IMU, modular electro-mechanical interface, and ARM based on-board control electronics.

IROS Conference 2014 Conference Paper

Expensive multiobjective optimization for robotics with consideration of heteroscedastic noise

Ryo Ariizumi
Matthew Tesch
Howie Choset
Fumitoshi Matsuno

In many robotic problems, optimization of the policy for multiple conflicting criteria is required. However this is very challenging due to the existence of noise, which may be input dependent, or heteroscedastic, and the restriction in the number of evaluations, due to robotic experiments which are expensive in time and/or money. This paper presents a multiobjective optimization (MOO) algorithm for expensive-to-evaluate noisy functions for robotics. We present a method for model selection between heteroscedastic and standard homoscedastic Gaussian process regression techniques to create suitable surrogate functions from noisy samples and find the point to be observed at the next step. This algorithm is compared against an existing MOO algorithm which assumes homoscedastic noise, and is then used to optimize the speed and head stability of the sidewinding gait of a snake robot.

IROS Conference 2014 Conference Paper

Guided locomotion in 3D for snake robots based on contact force optimization

Hugo Ponte
Matthew J. Travers
Howie Choset

The versatility of snake robots has led to their use in a wide variety of settings, including archaeological sites, natural disaster zones, and nuclear power plants. Currently, snake robots locomote through these rugged environments using repeatable pre-programmed motions, often with underwhelming performance. This paper presents the novel design of a control architecture that addresses the limitations of pre-programmed motions by using contact information from the environment. The controller uses contact force optimization, a concept taken from the field of manipulation, in combination with gain scheduling, to perturb existing gait controllers to perform better in three-dimensional environments. The efficacy of the controller is tested in a simulation of a snake robot on rugged terrain.

IROS Conference 2014 Conference Paper

Nonlinear dimensionality reduction for kinematic cartography with an application toward robotic locomotion

Tony Dear
Ross L. Hatton
Howie Choset

Planning robot motions often requires a notion of the “distance” between configurations or the “length” of a trajectory connecting them in the configuration space. If these quantities are defined so as to correspond to the effort required to change configurations, then they would likely differ from the Euclidean distance or arclength in the system's configuration parameters, distorting the visual representation of the relative costs of executing the motions. This problem is fundamentally similar to that of producing map projections with minimal distortion in cartography. A separate problem is that of nonlinear dimensionality reduction (NLDR), which, given a set of data, projects it into a lower-dimensional space while seeking to retain the geometric relationship between data points. In this paper, we show that NLDR can be applied to the kinematic cartography problem, allowing us to generate system parameterizations in which distance and arclength correspond to the effort of motion.

IROS Conference 2014 Conference Paper

Parameterized controller generation for multiple mode behavior

Chaohui Gong
Matthew J. Travers
Hsien-Tang Kao
Howie Choset

We derive and demonstrate a new capability for snake robots in which two behaviors-one for locomotion and the other for manipulation-are executed simultaneously on the same robot. This is done in two steps: 1) inverse kinematics via numerical optimization and 2) gait-based locomotion via modal decomposition. The result is an analytical representation of a multiple mode behavior that reduces online execution to simple parameterized control. This representation makes it possible to derive a feedback control law that enables reliable visual servoing using a snake robot while climbing a pole.

IROS Conference 2014 Conference Paper

Recursive dynamics and feedback linearizing control of serial-chain manipulators

Matthew J. Travers
Howie Choset

Manipulators that have the compliance necessary to share the same workspace and safely interact with people are currently of great interest to both the industrial as well as research communities. This work focuses on the development of nonlinear controllers for compliant serial-chain manipulators. In particular, we derive a novel algorithm that analytically computes feedback linearizing controllers for N-link manipulators with compliant joints. It is possible to express the controllers in closed form because we use geometric notation to concisely derive an algorithm that analytically inverts the manipulator's generalized inertia matrix. The resultant recursive dynamic expressions make it possible to solve for the feedback linearizing controllers exactly. Simulation results which apply the closed-form controllers to the analytic dynamics of a six-joint serial manipulator with series-elastic actuators are provided.

IROS Conference 2014 Conference Paper

Snakes on an inclined plane: Learning an adaptive sidewinding motion for changing slopes

Chaohui Gong
Matthew Tesch
David Rollinson
Howie Choset

Sidewinding is an efficient gait adopted by biological and robotic snakes for locomoting on various terrains. The mechanics of this motion on flat ground and steady state terrains have been thoroughly investigated, while its capability to adapt to changing environments is not as well studied. We demonstrate the capability of a snake robot to automatically adjust gait parameters to optimally move up and down slopes of varying angle. This capability is achieved by three components. First, an efficient offline learning algorithm finds a policy mapping the estimated slope angle to the optimal gait parameters. Next, a robust online state estimation technique infers the local terrain characteristics. Finally, the precomputed policy is consulted online to select the optimal gait parameters for this slope. The efficacy of this approach is verified by robot experiments.

IROS Conference 2014 Conference Paper

Torque control strategies for snake robots

David Rollinson
Kalyan Vasudev Alwala
Nico Zevallos
Howie Choset

We present three methods of achieving compliant motion with a snake robot by controlling the torques exerted by the joints of the robot. Two strategies command joint torques based solely on the robot's local curvature (i. e. joint angles). A third strategy commands joint angles, velocities, and torques based on the recorded feedback from the robot while executing a previously defined motion under position control. The three control strategies are implemented and compared on a snake robot that includes series elastic actuation (SEA) and torque sensing at each joint, and demonstrate compliant locomotion that adapts automatically to the robot's surrounding terrain.

IROS Conference 2014 Conference Paper

Using Lie algebra for shape estimation of medical snake robots

Rangaprasad Arun Srivatsan
Matthew J. Travers
Howie Choset

Highly articulated robots have the potential to play a key role in minimally invasive surgeries by providing improved access to hard-to-reach anatomy. Estimating their shape inside the body and combining it with 3D preoperative scans of the anatomy enable the surgeon to visualize how the entire robot interacts with the internal organs. As the robot progresses inside the body, the position and orientation of every link comprising the robot, evolves over a coordinate-free Lie algebra, se(3). To capture the full motion and uncertainty of the system, we use an extended Kalman filter where the state vector is defined using elements of se(3). We show that this approach describes the shape of the robot more accurately, than the ones where the state vector is a conventional parametrization, such as Cartesian coordinates and Euler angles. We perform two experiments to demonstrate the effectiveness of this new filtering approach.

ICRA Conference 2014 Conference Paper

Visual sensing for developing autonomous behavior in snake robots

Hugo Ponte
Max Queenan
Chaohui Gong
Christoph Mertz
Matthew J. Travers
Florian Enner
Martial Hebert
Howie Choset

Snake robots are uniquely qualified to investigate a large variety of settings including archaeological sites, natural disaster zones, and nuclear power plants. For these applications, modular snake robots have been tele-operated to perform specific tasks using images returned to it from an onboard camera in the robots head. In order to give the operator an even richer view of the environment and to enable the robot to perform autonomous tasks we developed a structured light sensor that can make three-dimensional maps of the environment. This paper presents a sensor that is uniquely qualified to meet the severe constraints in size, power and computational footprint of snake robots. Using range data, in the form of 3D pointclouds, we show that it is possible to pair high-level planning with mid-level control to accomplish complex tasks without operator intervention.

ICML Conference 2013 Conference Paper

Expensive Function Optimization with Stochastic Binary Outcomes

Matthew Tesch
Jeff G. Schneider
Howie Choset

Real world systems often have parameterized controllers which can be tuned to improve performance. Bayesian optimization methods provide for efficient optimization of these controllers, so as to reduce the number of required experiments on the expensive physical system. In this paper we address Bayesian optimization in the setting where performance is only observed through a stochastic binary outcome – success or failure of the experiment. Unlike bandit problems, the goal is to maximize the system performance after this offline training phase rather than minimize regret during training. In this work we define the stochastic binary optimization problem and propose an approach using an adaptation of Gaussian Processes for classification that presents a Bayesian optimization framework for this problem. We propose an experiment selection metric for this setting based on expected improvement. We demonstrate the algorithm’s performance on synthetic problems and on a real snake robot learning to move over an obstacle.

ICRA Conference 2013 Conference Paper

Expensive multiobjective optimization for robotics

Matthew Tesch
Jeff G. Schneider
Howie Choset

Many practical optimization problems in robotics involve multiple competing objectives - from design trade-offs to performance metrics of the physical system such as speed and energy efficiency. Proper treatment of these objective functions, while commonplace in fields such as economics, is often overlooked in robotics. Additionally, optimization of the performance of robotic systems can be restricted due to the expensive nature of testing control parameters on a physical system. This paper presents a multi-objective optimization (MOO) algorithm for expensive-to-evaluate functions that generates a Pareto set of solutions. This algorithm is compared against another leading MOO algorithm, and then used to optimize the speed and head stability of the sidewinding gait for a snake robot.

ICRA Conference 2013 Conference Paper

Extended gait equation for sidewinding

Chaohui Gong
Matthew J. Travers
Xiaozhou Fu
Howie Choset

Sidewinding is an efficient translational gait used by biological snakes to locomote over flat ground. Prior work has identified the fact that it is possible to steer the moving direction of sidewinding. The previously proposed virtual tread model reveals the working principal of sidewinding from a geometric point of view. Unfortunately, the implementation of the virtual tread model relied on a computationally expensive numerical fitting algorithm that impeded online applications. Motivated by this limitation, in this work we propose a novel approach to develop analytical expressions for snake robot gaits based on the study of the corresponding geometric model. This approach is rooted in the identification of dominant frequency components afforded by the two-dimensional Fast Fourier Transformation (FFT). Applying this method to the virtual tread model for conical sidewinding, we derive an analytical expression between the parameters that describe the gait's motion and the turning radius of the system moving in the world. This analytical expression, which we call the extended gait equation, is verified by experimental results.

ICRA Conference 2013 Conference Paper

Gait-based compliant control for snake robots

David Rollinson
Howie Choset

We present a method of achieving autonomous compliant behavior in snake robots. This behavior allows snake robots to adapt to changes in its environment, e. g. changes in pipe diameter while climbing. To simplify the task of high-level closed-loop control, the controller uses a low-dimensional gait framework that has been previously used for open-loop trajectory generation. We use an extended Kalman filter (EKF) to estimate the gait parameters that best represent the robot's shape, and then choose a control space of parameters relative to that state. Because this controller specifies whole-body motions of the robot, we are able to generate compliant behavior, even though the joints of the robot contain stiff gear ratios with no mechanical compliance or torque sensing.

ICRA Conference 2013 Conference Paper

Monocular feature-based periodic motion estimation for surgical guidance

Stephen Tully
George Kantor
Howie Choset

In this paper, we present a novel approach for mapping periodically moving visual features with a monocular camera. Our target application is the estimation of moving surfaces during minimally invasive surgery for the purpose of aiding in the guidance of surgical tools. Our approach uses a bank of Kalman filters to estimate FFT parameters that encode the periodic motion of visually detected features. To ensure convergent estimation for this highly nonlinear problem, we have developed an iterative update procedure that treats the Kalman filter measurement update step as an optimization problem. Unlike existing solutions that rely on stereo vision, our approach estimates periodic motion with a single moving camera. With an experiment involving a beating heart phantom, we have shown that our approach is able to successfully estimate the periodic motion of visual features.

ICRA Conference 2013 Conference Paper

Motion estimation of snake robots in straight pipes

Florian Enner
David Rollinson
Howie Choset

We present a method of estimating a snake robot's motion inside and outside of straight pipes using only knowledge of the robot's joint angles. We accomplish this by introducing a novel method to constructing a body frame for the robot that is aligned with the centerline of the pipe. In addition to greatly simplifying the motion model this method allows us to accurately estimate the diameter of the pipe. We present experimental results using a 16-DOF snake robot traversing the inside and outside of straight pipes.

ICRA Conference 2013 Conference Paper

ODrM* optimal multirobot path planning in low dimensional search spaces

Cornelia Ferner
Glenn Wagner
Howie Choset

We believe the core of handling the complexity of coordinated multiagent search lies in identifying which subsets of robots can be safely decoupled, and hence planned for in a lower dimensional space. Our work, as well as those of others take that perspective. In our prior work, we introduced an approach called subdimensional expansion for constructing low-dimensional but sufficient search spaces for multirobot path planning, and an implementation for graph search called M*. Subdimensional expansion dynamically increases the dimensionality of the search space in regions featuring significant robot-robot interactions. In this paper, we integrate M* with Meta-Agent Constraint-Based Search (MA-CBS), a planning framework that seeks to couple repeatedly colliding robots allowing for other robots to be planned in low-dimensional search space. M* is also integrated with operator decomposition (OD), an A*-variant performing lazy search of the outneighbors of a given vertex. We show that the combined algorithm demonstrates state of the art performance.

ICRA Conference 2013 Conference Paper

Snakes on a plan: Toward combining planning and control

Ross L. Hatton
Ross A. Knepper
Howie Choset
David Rollinson
Chaohui Gong
Enric Galceran

Highly articulated robot locomotion systems, such as snake robots, present special motion planning challenges. They possess many degrees of freedom, and therefore are modeled by a high dimensional configuration space which must be searched to plan a path. Kinematic and dynamic constraints further complicate the selection of effective controls. Finally, snake robots often have multiple modes of interaction with the terrain as contacts are made and broken, leading to complex and imperfect motion models. We believe that the space of useful controls that provides desirable motions, however, is much smaller. Useful net motions for such systems are often generated via gaits, or cyclic motions in the shape space. Gaits transform a high-dimensional continuum search into a relatively tractable discrete search. In this paper, we put forward a framework which allows a planner to generate paths in a low dimensional work space and select among gaits, pre-planned motions in the robot's shape space. The contribution of this paper rests on the “virtual chassis” which is a choice of body frame for the snake robot that allows the planner to efficiently select among and plan with gaits to direct the robot along the work space path. We demonstrate this planner running on a simulated snake robot navigating through a variety of clutter scenarios. The virtual chassis also has the benefit of allowing us to generalize notions of controllability to gait motions.

ICRA Conference 2012 Conference Paper

Conical sidewinding

Chaohui Gong
Ross L. Hatton
Howie Choset

Sidewinding is an efficient translation gait used by snakes and snake robots over flat ground, and resembles a helical tread moving over a core cylindrical geometry. Most sidewinding research has focused on straight-line translation of the snake, and less on steering capabilities. Here, we offer a new, geometrically intuitive method for steering this gait: Tapering the core cylinder into a cone, such that one end moves faster than the other, changing the heading of the robot as it drives forward. We present several design tools for working with this cone, along with experimental results on a physical robot turning at different rates.

ICRA Conference 2012 Conference Paper

Constrained filtering with contact detection data for the localization and registration of continuum robots in flexible environments

Stephen Tully
Andrea Bajo
George Kantor
Howie Choset
Nabil Simaan

This paper presents a novel filtering technique that uses contact detection data and environmental stiffness estimates to register and localize a robot with respect to an a priori 3D surface model. The algorithm leverages geometric constraints within a Kalman filter framework and relies on two distinct update procedures: 1) an equality constrained step for when the robot is forcefully contacting the environment, and 2) an inequality constrained step for when the robot lies in the free-space of the environment. This filtering procedure registers the robot by incrementally eliminating probabilistically infeasible state space regions until a high likelihood solution emerges. In addition to registration and localization, the algorithm can estimate the deformation of the surface model and can detect false positives with respect to contact estimation. This method is experimentally evaluated with an experiment involving a continuum robot interacting with a bench-top flexible structure. The presented algorithm produces an experimental error in registration (with respect to the end-effector position) of 1. 1 mm, which is less than 0. 8 percent of the robot length.

ICRA Conference 2012 Conference Paper

Design and architecture of the unified modular snake robot

Cornell Wright III
Austin D. Buchan
Ben Brown
Jason Geist
Michael Schwerin
David Rollinson
Matthew Tesch
Howie Choset

The design of a hyper-redundant serial-linkage snake robot is the focus of this paper. The snake, which consists of many fully enclosed actuators, incorporates a modular architecture. In our design, which we call the Unified Snake, we consider size, weight, power, and speed tradeoffs. Each module includes a motor and gear train, an SMA wire actuated bistable brake, custom electronics featuring several different sensors, and a custom intermodule connector. In addition to describing the Unified Snake modules, we also discuss the specialized head and tail modules on the robot and the software that coordinates the motion.

ICRA Conference 2012 Conference Paper

Multi-agent deterministic graph mapping via robot rendezvous

Chaohui Gong
Stephen Tully
George Kantor
Howie Choset

In this paper, we present a novel algorithm for deterministically mapping an undirected graph-like world with multiple synchronized agents. The application of this algorithm is the collective mapping of an indoor environment with multiple mobile robots while leveraging an embedded topological decomposition of the environment. Our algorithm relies on a group of agents that all depart from the same initial vertex in the graph and spread out to explore the graph. A centralized tree of graph hypotheses is maintained to consider loop-closure, which is deterministically verified when agents observe each other at a common vertex. To achieve efficient mapping, we introduce an active exploration method in which agents dynamically request rendezvous tasks from other available agents to validate graph hypotheses.

ICRA Conference 2012 Conference Paper

Over-tube apparatus for increasing the capabilities of an articulated robotic probe

Amir Degani
Stephen Tully
Brett Zubiate
Howie Choset

This video elaborates on a new active and controllable over-tube addition to the highly articulated robotic probe; the HARP. This over-tube allows the current HARP mechanism to double its overall length and allows it to perform more complex tasks. We explain the design concept of the current HARP and the novel over-tube mechanism and show two proof-of-concept experiments demonstrating the use of the active over-tube.

ICRA Conference 2012 Conference Paper

Probabilistic path planning for multiple robots with subdimensional expansion

Glenn Wagner
Minsu Kang
Howie Choset

Probabilistic planners such as Rapidly-Exploring Random Trees (RRTs) and Probabilistic Roadmaps (PRMs) are powerful path planning algorithms for high dimensional systems, but even these potent techniques suffer from the curse of dimensionality, as can be seen in multirobot systems. In this paper, we apply a technique called subdimensional expansion in order to enhance the performance of probabilistic planners for multirobot path planning. We accomplish this by exploiting the structure inherent to such problems. Subdimensional expansion initially plans in each individual robot's configuration space separately. It then couples those spaces when robots come into close proximity with one another. In this way, we constrain a probabilistic planner to search a low dimensional space, while dynamically generating a higher dimensional space where necessary. We show in simulation that subdimensional expansion enhanced PRMs can solve problems involving 32 robots and 128 total degrees of freedom in less than 10 minutes. We also demonstrate that enhancing RRTs and PRMs with subdimensional expansion can decrease the time required to find a solution by more than an order of magnitude.

ICRA Conference 2012 Conference Paper

Simplified motion modeling for snake robots

Florian Enner
David Rollinson
Howie Choset

We present a general method of estimating a snake robot's motion over flat ground using only knowledge of the robot's shape changes over time. Estimating world motion of snake robots is often difficult because of the complex way a robot's cyclic shape changes (gaits) interact with the surrounding environment. By using the virtual chassis to separate the robot's internal shape changes from its external motions through the world, we are able to construct a motion model based on the differential motion of the robot's modules between time steps. In this way, we effectively treat the snake robot like a wheeled robot where the bottom-most modules propel the robot in much the way the bottom of the wheels would propel the chassis of a car. Experimental results using a 16-DOF snake robot are presented to demonstrate the effectiveness of this method for a variety of gaits that have been designed to traverse flat ground.

SoCS Conference 2012 Conference Paper

Subdimensional Expansion and Optimal Task Reassignment

Glenn Wagner
Howie Choset
Nora Ayanian

Multirobot path planning and task assignment are traditionally treated separately, however task assignment can greatly impact the difficulty of the path planning problem, and the ultimate quality of solution is dependent upon both. We introduce task reassignment, an approach to optimally solving the coupled task assignment and path planning problems. We show that task reassignment improves solution quality, and reduces planning time in some situations.

IROS Conference 2011 Conference Paper

Adapting control policies for expensive systems to changing environments

Matthew Tesch
Jeff G. Schneider
Howie Choset

Many controlled systems must operate over a range of external conditions. In this paper, we focus on the problem of learning a policy to adapt a system's controller based on the value of these external conditions in order to always perform well (i. e. , maximize system output). In addition, we are concerned with systems for which it is expensive to run experiments, and therefore restrict the number that can be run during training. We formally define the problem setup and the notion of an optimal control policy. We propose two algorithms which aim to find such a policy while minimizing the number of system output evaluations. We present results comparing these algorithms and various other approaches and discuss the inherent tradeoffs in the proposed algorithms. Finally, we use these methods to train both simulated and physical snake robots to automatically adapt to changing terrain, and demonstrate improved performance on test courses with changing environments.

IROS Conference 2011 Conference Paper

Geometric maneuverability with applications to low reynolds number swimming

Ross L. Hatton
Lisa J. Burton
Anette E. Hosoi
Howie Choset

A mobile system's maneuverability describes the scale and span of the velocities with which it can move. In this paper, we present a new geometric framework for describing the maneuverability of kinematic locomoting systems, inspired by the manipulability analysis of robotic arms. This framework describes both the local maneuverability in the neighborhood of each shape the system can assume and the cyclic maneuverability achieved by executing gaits from a library. Additionally, the gait-level analysis includes tools that direct the search for gaits whose inclusion into the library will usefully improve the maneuverability. Throughout, we provide examples based on a swimming system operating at low Reynolds number.

ICRA Conference 2011 Conference Paper

Incremental construction of the saturated-GVG for multi-hypothesis topological SLAM

Tong Tao
Stephen Tully
George Kantor
Howie Choset

The generalized Voronoi graph (GVG) is a topological representation of an environment that can be incrementally constructed with a mobile robot using sensor-based control. However, because of sensor range limitations, the GVG control law will fail when the robot moves into a large open area. This paper discusses an extended GVG approach to topological navigation and mapping: the saturated generalized Voronoi graph (S-GVG), for which the robot employs an additional wall-following behavior to navigate along obstacles at the range limit of the sensor. In this paper, we build upon previous work related to the S-GVG and provide two important contributions: 1) a rigorous discussion of the control laws and algorithm modifications that are necessary for incremental construction of the S-GVG with a mobile robot, and 2) a method for incorporating the S-GVG into a novel multi-hypothesis SLAM algorithm for loop-closing and localization. Experiments with a wheeled mobile robot in an office-like environment validate the effectiveness of the proposed approach.

IROS Conference 2011 Conference Paper

Inequality constrained Kalman filtering for the localization and registration of a surgical robot

Stephen Tully
George Kantor
Howie Choset

We present a novel method for enforcing nonlinear inequality constraints in the estimation of a high degree of freedom robotic system within a Kalman filter. Our constrained Kalman filtering technique is based on a new concept, which we call uncertainty projection, that projects the portion of the uncertainty ellipsoid that does not satisfy the constraint onto the constraint surface. A new PDF is then generated with an efficient update procedure that is guaranteed to reduce the uncertainty of the system. The application we have targeted for this work is the localization and automatic registration of a robotic surgical probe relative to preoperative images during image-guided surgery. We demonstrate the feasibility of our constrained filtering approach with data collected from an experiment involving a surgical robot navigating on the epicardial surface of a porcine heart.

IROS Conference 2011 Conference Paper

M*: A complete multirobot path planning algorithm with performance bounds

Glenn Wagner
Howie Choset

Multirobot path planning is difficult because the full configuration space of the system grows exponentially with the number of robots. Planning in the joint configuration space of a set of robots is only necessary if they are strongly coupled, which is often not true if the robots are well separated in the workspace. Therefore, we initially plan for each robot separately, and only couple sets of robots after they have been found to interact, thus minimizing the dimensionality of the search space. We present a general strategy called subdimensional expansion, which dynamically generates low dimensional search spaces embedded in the full configuration space. We also present an implementation of subdimensional expansion for robot configuration spaces that can be represented as a graph, called M*, and show that M* is complete and finds minimal cost paths.

IROS Conference 2011 Conference Paper

Monte Carlo Localization using 3D texture maps

Yu Fu
Stephen Tully
George Kantor
Howie Choset

This paper uses KLD-based (Kullback-Leibler Divergence) Monte Carlo Localization (MCL) to localize a mobile robot in an indoor environment represented by 3D texture maps. A 3D texture map is a simplified model that includes vertical planes with colored texture information associated with each vertical plane. At each time step, a distance measurement and an observed texture from an omnidirectional camera are compared to the expected distance measurement and the expected texture according to each hypothesis of the robot's pose in an MCL framework. Compared to previous implementations of MCL, our proposed approach converges faster than distance-only MCL and localizes the robot more precisely than SIFT-based MCL. We demonstrate this new MCL algorithm for robot localization with experiments in several hallways.

IROS Conference 2011 Conference Paper

Shape estimation for image-guided surgery with a highly articulated snake robot

Stephen Tully
George Kantor
Marco A. Zenati
Howie Choset

In this paper, we present a filtering method for estimating the shape and end effector pose of a highly articulated surgical snake robot. Our algorithm introduces new kinematic models that are used in the prediction step of an extended Kalman filter whose update step incorporates measurements from a 5-DOF electromagnetic tracking sensor situated at the distal end of the robot. A single tracking sensor is sufficient for estimating the shape of the system because the robot is inherently a follow-the-leader mechanism with well defined motion characteristics. We therefore show that, with appropriate steering motion, the state of the filter is fully observable. The goal of our shape estimation algorithm is to create a more accurate and representative 3D rendered visualization for image-guided surgery. We demonstrate the feasibility of our method with results from an animal experiment in which our shape and pose estimate was used as feedback in a control scheme that semi-autonomously drove the robot along the epicardial surface of a porcine heart.

IROS Conference 2011 Conference Paper

State estimation for snake robots

David Rollinson
Austin D. Buchan
Howie Choset

We present a comparison of methods to estimate the shape and orientation of a locomoting snake robot by fusing the robot's redundant internal proprioceptive sensors using and Extended Kalman Filter (EKF). All of the estimators used in this work represent the shape of the snake with gait parameters to reduce the complexity of the robot configuration space. The compared approaches for representing shape and pose of the snake robot differ primarily in the use of a body frame fixed to the pose of a single module versus one that is aligned with the virtual chassis. Additionally, we evaluate a state representation that explicitly tracks joint angles for improved estimates. For one particular gait, rolling, we present experimental data where motion capture data of the snake robot is used as ground truth to compare the accuracy of the state estimates from these techniques. We show that using the virtual chassis body frame, rather than a fixed body frame, results in improved accuracy of the snake robot's estimated pitch and roll. We also show that, in general, representing the robot's shape with gait parameters is sufficient to accurately estimated shape and pose, though it can be improved upon in specific cases by explicitly modeling joint angles.

ICRA Conference 2011 Conference Paper

The ParkourBot - a dynamic BowLeg climbing robot

Amir Degani
Siyuan Feng 0003
H. Benjamin Brown
Kevin M. Lynch
Howie Choset
Matthew T. Mason

The ParkourBot is an efficient and dynamic climbing robot. The robot comprises two springy legs connected to a body. Leg angle and spring tension are independently controlled. The robot climbs between two parallel walls by leaping from one wall to the other. During flight, the robot stores elastic energy in its springy legs and automatically releases the energy to “kick off” the wall during touch down. This paper elaborates on the mechanical design of the ParkourBot. We use a simple SLIP model to simulate the ParkourBot motion and stability. Finally, we detail experimental results, from open-loop climbing motions to closed-loop stabilization of climbing height in a planar, reduced gravity environment.

IROS Conference 2011 Conference Paper

Using response surfaces and expected improvement to optimize snake robot gait parameters

Matthew Tesch
Jeff G. Schneider
Howie Choset

Several categories of optimization problems suffer from expensive objective function evaluation, driving the need for smart selection of subsequent experiments. One such category of problems involves physical robotic systems, which often require significant time, effort, and monetary expenditure in order to run tests. To assist in the selection of the next experiment, there has been a focus on the idea of response surfaces in recent years. These surfaces interpolate the existing data and provide a measure of confidence in their error, serving as a low-fidelity surrogate function that can be used to more intelligently choose the next experiment. In this paper, we robustly implement a previous algorithm based on the response surface methodology with an expected improvement criteria. We apply this technique to optimize open-loop gait parameters for snake robots, and demonstrate improved locomotive capabilities.

IROS Conference 2011 Conference Paper

Virtual chassis for snake robots

David Rollinson
Howie Choset

We present a new method of defining a body coordinate frame for locomoting snake robots. Representing the motion of snake robots from the perspective of the robot is difficult because the internal shape changes that the robot uses to locomote interact with world in a complex way. Therefore, rather than representing the system in a body frame that is static to some fixed point on a link, we instead define a body frame that is consistent with the overall shape of the robot in all configurations. We are able to define such a body frame by continuously aligning it with the principal moments of inertia taken at the center of mass of the robot. In some cases we are able to further exploit symmetry in the shape of the robot's cyclic motion (gait), and use non-linear optimization to more precisely align the body frame with the true axis of symmetry of the robot's shape. These shape stable body frames serve as virtual chassis that effectively separate the internal motion of a gait from the external motion due to that gait's interaction with the world. Furthermore, these body frames allow the motion of the robot to be described in a way that is well-aligned with one's intuitive notions of position and orientation that arise when considering the system as a whole.

AAAI Conference 2010 Conference Paper

A Single-Step Maximum A Posteriori Update for Bearing-Only SLAM

Stephen Tully
George Kantor
Howie Choset

This paper presents a novel recursive maximum a posteriori update for the Kalman formulation of undelayed bearing-only SLAM. The estimation update step is cast as an optimization problem for which we can prove the global minimum is reachable via a bidirectional search using Gauss-Newton’s method along a one-dimensional manifold. While the filter is designed for mapping just one landmark, it is easily extended to full-scale multiple-landmark SLAM. We provide this extension via a formulation of bearing-only FastSLAM. With experiments, we demonstrate accurate and convergent estimation in situations where an EKF solution would diverge.

ICRA Conference 2010 Conference Paper

DSAC - Dynamic, Single Actuated Climber: Local stability and bifurcations

Amir Degani
Howie Choset
Matthew T. Mason

This paper investigates a novel mechanism, called DSAC for Dynamic, Single Actuated Climber, which propels itself upwards by oscillating its leg in a symmetric fashion using a single actuator. This mechanism achieves dynamic, vertical motion while retaining simplicity in design and control. We explore the local orbital stability of the DSAC mechanism. We use the Poincaré map method with a well chosen Poincaré section to simplify the problem by reducing the dimension of the Poincaré map to 3-dimensions. We find the stable regions while varying the controls input and some of the mechanism's parameters. Moreover, in response to a continuous change in a parameter of the mechanism, the symmetric and steady stable gait of the mechanism gradually evolves through a regime of period doubling bifurcations.

ICRA Conference 2010 Conference Paper

Minimalistic, dynamic, tube climbing robot

Amir Degani
Siyuan Feng 0003
Howie Choset
Matthew T. Mason

This video shows the investigation of a novel minimalistic, dynamic climbing robot which can climb up tubes of different shapes using a simple dc motor. The motor moves an eccentric mass in a constant velocity. The location of the eccentric mass relative to the contact point determines the stability and the direction of the climbing motion. We present the analysis of this mechanism, simulation and experimental results.

ICRA Conference 2010 Conference Paper

Optimizing coordinate choice for locomoting systems

Ross L. Hatton
Howie Choset

Gait evaluation techniques that use Stokes's theorem to integrate a system's equations of motion have traditionally been limited to finding only the net rotations or small translations produced by gaits. Recently, we have observed that certain choices of generalized coordinates allow these techniques to be extended to gaits that produce large translations. In this paper, we present a method for finding the optimal coordinate choice for this purpose, based on a Hodge-Helmholtz decomposition of the system constraints, and demonstrate the efficacy of the Stokes's theorem approach over a wide variety of gaits when using the optimized coordinate choice.

ICRA Conference 2010 Conference Paper

Sidewinding on slopes

Ross L. Hatton
Howie Choset

Sidewinding is an efficient translation gait used by snakes over flat ground. When implemented on snake robots, it retains its general effectiveness, but becomes unstable on sloped surfaces. Flattening the sidewinding motion along the surface to provide a more stable base corrects for this instability, but degrades other performance characteristics, such as efficiency and handling of rough terrain. In this paper, we identify stability conditions for a sidewinder on a slope and find a solution for the minimum aspect ratio of the sidewinding pattern needed to maintain stability. Our theoretical results are supported by experiments on snake robots. In constructing our stability analysis, we present a new, tread-based model for sidewinding that is both consistent with previous models and provides new intuition regarding the kinematics of the gait. This new interpretation of sidewinding further admits a symmetry-based model reduction that simplifies its analysis. Additionally, an intermediate stage of the theoretical work contains a comprehensive analysis of the behavior of an ellipse in rolling contact with a sloped surface.

IROS Conference 2009 Conference Paper

A multi-hypothesis topological SLAM approach for loop closing on edge-ordered graphs

Stephen Tully
George Kantor
Howie Choset
Felix Werner

We present a method for topological SLAM that specifically targets loop closing for edge-ordered graphs. Instead of using a heuristic approach to accept or reject loop closing, we propose a probabilistically grounded multi-hypothesis technique that relies on the incremental construction of a map/state hypothesis tree. Loop closing is introduced automatically within the tree expansion, and likely hypotheses are chosen based on their posterior probability after a sequence of sensor measurements. Careful pruning of the hypothesis tree keeps the growing number of hypotheses under control and a recursive formulation reduces storage and computational costs. Experiments are used to validate the approach.

IROS Conference 2009 Conference Paper

Generating gaits for snake robots by annealed chain fitting and Keyframe wave extraction

Ross L. Hatton
Howie Choset

Snake robots have many degrees of freedom, which makes them both extremely versatile and complex to control. In this paper, we address this complexity by introducing two algorithms. Annealed chain fitting efficiently maps a continuous backbone curve to a set of joint angles for a snake robot. Keyframe wave extraction takes joint angles fit to a sequence of backbone curves, and identifies parameterized periodic functions which produce those sequences. Together, they allow a designer to conceive a gait in terms three-dimensional shapes and translate them into easily manipulated wave functions. We validate the algorithms by using them to produce rolling gaits for crawling and climbing.

IROS Conference 2009 Conference Paper

Topological SLAM using neighbourhood information of places

Felix Werner
Frédéric Maire
Joaquin Sitte
Howie Choset
Stephen Tully
George Kantor

Perceptual aliasing makes topological navigation a difficult task. In this paper we present a general approach for topological SLAM (simultaneous localisation and mapping) which does not require motion or odometry information but only a sequence of noisy measurements from visited places. We propose a particle filtering technique for topological SLAM which relies on a method for disambiguating places which appear indistinguishable using neighbourhood information extracted from the sequence of observations. The algorithm aims to induce a small topological map which is consistent with the observations and simultaneously estimate the location of the robot. The proposed approach is evaluated using a data set of sonar measurements from an indoor environment which contains several similar places. It is demonstrated that our approach is capable of dealing with severe ambiguities and, and that it infers a small map in terms of vertices which is consistent with the sequence of observations.

ICRA Conference 2008 Conference Paper

An optimization approach to planning for mobile manipulation

Dmitry Berenson
James J. Kuffner
Howie Choset

We present an optimization-based approach to grasping and path planning for mobile manipulators. We focus on pick-and-place operations, where a given object must be moved from its start configuration to its goal configuration by the robot. Given only the start and goal configurations of the object and a model of the robot and scene, our algorithm finds a grasp and a trajectory for the robot that will bring the object to its goal configuration. The algorithm consists of two phases: optimization and planning. In the optimization phase, the optimal robot configurations and grasp are found for the object in its start and goal configurations using a co-evolutionary algorithm. In the planning phase, a path is found connecting the two robot configurations found by the optimization phase using Rapidly-Exploring Random Trees (RRTs). We benchmark our algorithm and demonstrate it on a 10 DOF mobile manipulator performing complex pick-and-place tasks in simulation.

ICRA Conference 2008 Conference Paper

Iterated filters for bearing-only SLAM

Stephen Tully
Hyungpil Moon
George Kantor
Howie Choset

This paper discusses the importance of iteration when performing the measurement update step for the problem of bearing-only SLAM. We focus on an undelayed approach that initializes a landmark after only one bearing measurement. Traditionally, the extended Kalman filter (EKF) has been used for SLAM, but the EKF measurement update rule can often lead to a divergent state estimate due to its inconsistency in linearization. We discuss the flaws of the EKF in this paper, and show that even the well established inverse-depth parametrization for bearing-only SLAM can be affected. We then show that representing the bearing-only update as a numerical optimization problem (solved with an iterative approach such as Gauss-Newton minimization) prevents divergence of the Kalman filter state and produces accurate SLAM results for a bearing-only sensor. More specifically, we propose the use of an iterated Kalman filter to resolve the issues normally associated with the EKF measurement update. Two outdoor mobile robot experiments are discussed to compare algorithm performance.

ICRA Conference 2008 Conference Paper

Toroidal skin drive for snake robot locomotion

James C. McKenna
David J. Anhalt
Frederick M. Bronson
H. Benjamin Brown
Michael Schwerin
Elie A. Shammas
Howie Choset

Small robots have the potential to access confined spaces where humans cannot go. However, the mobility of wheeled and tracked systems is severely limited in cluttered environments. Snake robots using biologically inspired gaits for locomotion can provide better access in many situations, but are slow and can easily snag. This paper introduces an alternative approach to snake robot locomotion, in which the entire surface of the robot provides continuous propulsive force to significantly improve speed and mobility in many environments.

IROS Conference 2007 Conference Paper

A dynamic single actuator vertical climbing robot

Amir Degani
Amir Shapiro
Howie Choset
Matthew T. Mason

A climbing robot mechanism is introduced, which uses dynamic movements to climb between two parallel vertical walls. This robot relies on its own internal dynamic motions to gain height, unlike previous mechanisms which are quasi- static. One benefit of dynamics is that it allows climbing with only a single actuated degree of freedom. We show with analysis, simulations and experiments that this dynamic robot is capable of climbing vertically between parallel walls. We introduce simplifications that enable us to obtain closed form approximations of the robot motion. Furthermore, this provides us with some design considerations and insights into the mechanism's ability to climb.

IROS Conference 2007 Conference Paper

Context identification for efficient multiple-model state estimation

Sarjoun Skaff
Alfred A. Rizzi
Howie Choset

This paper presents an approach to accurate and scalable multiple-model state estimation for hybrid systems with intermittent, multi-modal dynamics. The approach consists of using discrete-state estimation to identify a system’s behavioral context and determine which motion models appropriately represent current dynamics, and which multiple-model filters are appropriate for state estimation. This improves the accuracy and scalability of conventional multiple-model state estimation. This approach is validated experimentally on a mobile robot that exhibits multi-modal dynamics.

IROS Conference 2007 Conference Paper

Design and control of a second-generation hyper-redundant mechanism

H. Benjamin Brown
Michael Schwerin
Elie A. Shammas
Howie Choset

We present a refined, second-generation design, construction and integration, of a compact hyper-redundant snakelike robot, called "Woodstock. " This robot has substantial advantages over our previous design iteration, "Snoopy, " in terms of cost and performance. The robot is composed of six actuated universal joints which are serially chained to construct a twelve degrees of freedom snake-like robot optimized for strength and compactness. Any joint in the robot is strong enough to produce a torque that is capable of cantilevering the entire robot. This paper also presents the low-level system- control architecture, which is based on a high-speed RS-485 data bus; this allows the entire system to be operated with only two power and two data wires. The system is controlled from a remote computer on a wireless network and can also run over the Internet.

IROS Conference 2007 Conference Paper

Design of a modular snake robot

Cornell Wright III
Aaron M. Johnson 0001
Aaron Peck
Zachary McCord
Allison Naaktgeboren
Philip Gianfortoni
Manuel González-Rivero
Ross L. Hatton

Many factors such as size, power, and weight constrain the design of modular snake robots. Meeting these constraints requires implementing a complex mechanical and electrical architecture. Here we present our solution, which involves the construction of sixteen aluminum modules and creation of the Super Servo, a modified hobby servo. To create the Super Servo, we have replaced the electronics in a hobby servo, adding such components as sensors to monitor current and temperature, a communications bus, and a programmable microcontroller. Any robust solution must also protect components from hazardous environments such as sand and brush. To resolve this problem we insert the robots into skins that cover their surface. Functions such as climbing the inside and outside of a pipe add a new dimension of interaction. Thus we attach a compliant, high-friction material to every module, which assists in tasks that require gripping. This combination of the mechanical and electrical architectures results in a robust and versatile robot.

IROS Conference 2007 Conference Paper

Differentiable and piecewise differentiable gaits for snake robots

Kevin Lipkin
Isaac Brown
Aaron Peck
Howie Choset
Justine Rembisz
Philip Gianfortoni
Allison Naaktgeboren

This paper describes a series of gaits which we developed for a free crawling snake robot. Snake robots, a class of hyper-redundant mechanisms, can use their many degrees of freedom to achieve a variety of locomotion capabilities. Like their biological counterparts, snake robots locomote using cyclic motions called gaits. These cyclic motions directly control the snake robot's internal degrees of freedom which causes a net motion (e. g. sining moves the robot forward, strafing moves the robot laterally, and spinning rotates the robot about its center). The gaits described in this paper fall into two categories: differentiable and piecewise differentiable. The differentiable gaits, as their name suggests, can be described by a differentiable function whereas the piecewise cannot. This paper describes the functions we prescribed for gait generation and our experiences in making these robots operate in real experiments.

ICRA Conference 2007 Conference Paper

Frictional Compliance Model Development and Experiments for Snake Robot Climbing

Amir Shapiro
Aaron Greenfield
Howie Choset

Intelligently utilizing the frictional contact between a robot and its environment can prevent slip, maintain balance, and provide stability during a robot's motion. A contact model is first needed to enable robot control achieving these goals. The model should be both accurate and simple enough to allow further system analysis. In this paper we propose a simple parametric contact model, based on the form of the Hertz-Walton model. We experimentally demonstrate that this contact model can be effectively used to predict contact forces for linear and near-linear loading paths. Finally, we briefly discuss the applicability of the presented contact model for snake robot climbing. The control of the snake robot is based on stabilizing a sequence of set points.

IROS Conference 2007 Conference Paper

Hybrid localization using the hierarchical atlas

Stephen Tully
Hyungpil Moon
Deryck Morales
George Kantor
Howie Choset

This paper presents a hybrid localization scheme for a mobile robot using the hierarchical atlas. The hierarchical atlas is a map that consists of a higher level topological graph with lower level feature-based metric submaps associated with the graph edges. Our method employs both a discrete Bayes filter and a Kalman filter to localize the robot in the map. This framework accommodates localization in a map with no prior information (global localization) and localization in a map with an incorrect pose estimate (kidnapped robot). Our approach efficiently scales to large environments without sacrificing accuracy or robustness. We have verified our method with large-scale experiments in a multi-floor office environment.

IROS Conference 2007 Conference Paper

Valet parking without a valet

David C. Conner
Hadas Kress-Gazit
Howie Choset
Alfred A. Rizzi
George J. Pappas

What would it be like if we could give our robot high level commands and it would automatically execute them in a verifiably correct fashion in dynamically changing environments? This work demonstrates a method for generating continuous feedback control inputs that satisfy high-level specifications. Using a collection of continuous local feedback control policies in concert with a synthesized discrete automaton, this paper demonstrates the approach on an Ackermann-steered vehicle that satisfies the command "drive around until you find an empty parking space, then park. " The system reacts to changing environmental conditions using only local information, while guaranteeing the correct high level behavior. The local policies consider the vehicle body shape as well as bounds on drive and steering velocities. The discrete automaton that invokes the local policies guarantees executions that satisfy the high-level specification based only on information about the current availability of the nearest parking space. This paper also demonstrates coordination of two vehicles using the approach.

ICRA Conference 2006 Conference Paper

Highly Articulated Robotic Probe for Minimally Invasive Surgery

Amir Degani
Howie Choset
Alon Wolf
Marco A. Zenati

We have developed a novel highly articulated robotic probe (HARP) that can thread through tightly packed volumes without disturbing the surrounding tissues and organs. We use cardiac surgery as the focal application of this work. As such, we have designed the HARP to enter the pericardial cavity through a subxiphoid port. The surgeon can effectively reach remote intrapericardial locations on the epicardium and deliver therapeutic interventions under direct control. Reducing the overall cross-sectional diameter of the mechanism was the main challenge in the design of this device. Our device differs from others in that we use conventional actuation and still have good maneuverability. We have performed simple proof-of-concept clinical experiments to give preliminary validation of the ideas presented here

ICRA Conference 2006 Conference Paper

Towards Automated Gait Generation for Dynamic Systems with Non-holonomic Constraints

Elie A. Shammas
Howie Choset
Alfred A. Rizzi

In this paper we generate gaits for dynamics systems that are subject to non-holonomic velocity constraints. These systems are referred to as mixed non-holonomic systems. The motion of such systems is governed by both the non-holonomic constraints acting on the system and a system of differential equations constraining the evolution of generalized momentum. We propose a method that utilizes both governing motions, that is, satisfying all the constraints and instantaneously conserving momentum along un-restricted directions, to generate gaits for systems like the snakeboard, which belongs to the family of mixed non-holonomic systems. We accomplish this by defining a new scaled momentum variable. This scaled momentum allows us to easily explore the design of gaits that causes momentum to evolve such that a desired non-trivial motion results

ICRA Conference 2005 Conference Paper

A Context-Based State Estimation Technique for Hybrid Systems

Sarjoun Skaff
Alfred A. Rizzi
Howie Choset
Pei-Chun Lin

This paper proposes an approach to robust state estimation for mobile robots with intermittent dynamics. The approach consists of identifying the robot’s mode of operation by classifying the output of onboard sensors into mode-specific contexts. The underlying technique seeks to efficiently use available sensor information to enable accurate, high-bandwidth mode identification. Context classification is combined with multiple-model filtering in order to significantly improve the accuracy of state estimates for hybrid systems. This approach is validated in simulation and shown experimentally to produce accurate estimates on a jogging robot using low-cost sensors.

ICRA Conference 2005 Conference Paper

Dynamic Ambiguities in Frictional Rigid-body Systems with Application to Climbing via Bracing

Aaron Greenfield
Alfred A. Rizzi
Howie Choset

Constructing climbing behaviors for hyper-redundant robots that account for the system dynamics requires a model of robot dynamics under contact and friction. One common model, rigid-body dynamics with coulomb friction, unfortunately is both an ambiguous and inconsistent set of dynamic axioms. This paper addresses the ambiguity problem by developing an algorithm which computes the set of joint torques such that all solutions are guaranteed to produce the desired system behavior. This algorithm is applied to a type of robot climbing which we denote climbing via bracing where a hyper-redundant robot stabilizes itself against gravity by pressing outward to induce friction. By bracing with a fraction of the robot, which we term a brace the remainder of the robot remains free to move upward and brace at a higher location. A sequence of braces thus moves the robot upward.

ICRA Conference 2005 Conference Paper

Hierarchical Segmentation of Surfaces Embedded in R3 for Auto-Body Painting

Prasad N. Atkar
Aaron Greenfield
David C. Conner
Howie Choset
Alfred A. Rizzi

Complete automation of trajectory planning tools for material deposition/removal applications has become increasingly necessary to reduce the “concept-to-consumer” timeline in product development. Segmentation of a complex automotive surfaces into topologically simple surfaces remains a barrier in the automation of trajectory generation. In this paper, we develop a novel hierarchical procedure to segment a complex automotive surface into geometrically as well as topologically simple components.

ICRA Conference 2005 Conference Paper

Natural Gait Generation Techniques for Multi-bodied Isolated Mechanical Systems

Elie A. Shammas
Klaus Schmidt 0002
Howie Choset

This paper investigates how to generate cyclic gaits for multi-bodied isolated mechanical systems whose configuration space is represented by a trivial fiber bundle. We describe how to generate gaits in the base space of the fiber bundle, or the shape space of the robot on which we assume full control. Such gaits are guaranteed to generate a non-zero motion along the fiber space, i. e. , a net change in the position of the robot, while making sure that the robot’s shape is unchanged after a complete cycle. The gait generation technique presented in this paper is intuitive; it involves dividing the base space into well defined regions and devising a set of simple rules on how to generate curves in such regions. Not only do such curves guarantee non-zero position change but also do allow for gait optimization.

ICRA Conference 2005 Conference Paper

Sensor-based Planning for Planar Multi-Convex Rigid Bodies

Ji Yeong Lee
Howie Choset

This paper presents a method for a planar rigid body consisting of multiple convex bodies to explore an unknown planar workspace, i. e. , an unknown configuration space diffeomorphic to SE(2). This method is based on a roadmap termed concave hierarchical generalized Voronoi graph (concave-HGVG). Just as in our previous work, we decompose the free configuration space into contractible cells in which we define the concave generalized Voronoi graphs (concave-GVG), and then connect these graphs using an additional structure termed one-tangent edges. Since the robot consists of multiple convex bodies, the one-tangent edges are defined using the diameter function of the convex hull of the convex bodies as well as the individual convex bodies. These two structures together form the concave-HGVG, which is a one-dimensional roadmap of the multi-convex bodies in plane. Both components are defined in terms of workspace distance measurement, and thus the concave-HGVG can readily be constructed in a sensor-based way.

ICRA Conference 2004 Conference Paper

Arc Carving: Obtaining Accurate, Low Latency Maps from Ultrasonic Range Sensors

David Silver 0002
Deryck Morales
Ioannis M. Rekleitis
Brad Lisien
Howie Choset

In this paper we present a new technique for improving the azimuth resolution of ultrasonic range sensors frequently used with mobile robots. This improvement is achieved without a significant increase in the latency, or processing delay, of the system. Our approach decreases the azimuth uncertainty of a sensor reading by eliminating portions of the reading that are contradicted by subsequent readings. Our idea bears resemblance to space carving as used by the vision community, where a ray of light is used to define the boundaries of an obstacle. A sonar model similar to that commonly utilized by occupancy grids is used. Our method, termed arc carving, can be used to produce maps that are both accurate and with low enough latency for robust mobile robot navigation. Experimental results verify this approach over spaces as large as 5000 square meters.

ICRA Conference 2004 Conference Paper

Bearing-only Landmark Initialization with Unknown Data Association

Albert Costa
George Kantor
Howie Choset

It is essential in many applications that mobile robots localize themselves with respect to an unknown environment. This means that the robot must build a map of its environment and then localize using the map. This process is called simultaneous localization and mapping (SLAM). This paper presents an iterative solution to the landmark initialization problem inherent in a bearing-only implementation of SLAM. No prior knowledge of the environment is required, and furthermore, there are no requirements about having the data association problem solved. Once landmarks are initialized, they are inserted into an extended Kalman Filter (EKF) to solve the SLAM problem. Both indoor and outdoor experiments are presented to validate the method.

ICRA Conference 2004 Conference Paper

Design of a High-impact Survivable Robot

Daniel O'Halloran
Alon Wolf
Howie Choset

This paper presents the design, construction, and testing of a two-wheeled low-cost mobile robot platform that has high survivability when subjected to large impact forces and general rough handling. The design of the drive transmission system and integrated suspension system is developed, along with general equations of motion describing their dynamics. Analyses were conducted to insure stability of the various subsystems and optimize parameters for the desired vibration characteristics. Equations of motion were also developed to describe the rocking chassis phenomenon inherent to the two-wheeled design. A flywheel compensation scheme which helps eliminate the rocking chassis problem is also outlined. An impact analysis combining theory and empirical data was used to predict the survivability threshold. Finally, three series of experiments were conducted, with the first two followed by design improvements. In contrast to currently available commercial robots, our new design employs a flexible mechanical platform capable of absorbing energy during high load impacts. This design was substantiated during the final tests when the robot survived a third story drop without any damage.

ICRA Conference 2004 Conference Paper

Development and Deployment of a Line of Sight Virtual Sensor for Heterogeneous Teams

Robert Grabowski
Pradeep K. Khosla
Howie Choset

For a team of cooperating robots, geometry plays a vital role in operation. Knowledge of line of sight to local obstacles and adjacent teammates is critical in both the movement and planning stages to avoid collisions, maintain formation and localize the team. However, determining if other robots are within the line of sight of one another is difficult with existing sensor platforms - especially as the scale of the robot is reduced. We describe a method of exploiting collective team information to generate a virtual sensor that provides line of sight determination, greater range and resolution and the ability to generalize local sensing. We develop this sensor and apply it to the control of a tightly coupled, resource-limited robot team called Millibots.

ICRA Conference 2004 Conference Paper

Limited Communication, Multi-robot Team Based Coverage

Ioannis M. Rekleitis
Vincent Lee-Shue
Ai Peng New
Howie Choset

This paper presents an algorithm for the complete coverage of free space by a team of mobile robots. Our approach is based on a single robot coverage algorithm, which divides the target two-dimensional space into regions called cells, each of which can be covered with simple back-and-forth motions; the decomposition of free space in a collection of such cells is known as Boustrophedon decomposition. Single robot coverage is achieved by ensuring that the robot visits every cell. The new multi-robot coverage algorithm uses the same planar cell-based decomposition as the single robot approach, but provides extensions to handle how teams of robots cover a single cell and how teams are allocated among cells. This method allows planning to occur in a two-dimensional configuration space for a team of N robots. The robots operate under the restriction that communication between two robots is available only when they are within line of sight of each other.

ICRA Conference 2004 Conference Paper

Motion Planning for a Rod-shaped Robot in ℝ 3: Connecting the Rod-HGVG using the Point-HGVG

Ji Yeong Lee
Howie Choset

This work considers the motion planning for a rod-shaped robot in a three-dimensional space. Our approach is to construct a roadmap in the configuration space of the rod and use it to navigate and map unknown spaces. Previously, we defined the rod-HGVG, which is a roadmap for a rod-shaped robot operating in a three-dimensional space. However, the rod-HGVG is only guaranteed to be connected if the point-GVG is connected. This work extends the rod-HGVG into more general environments where the point-GVG may not be connected but the point-HGVG is connected. For this, we define new components, termed the higher-order edges for the rod-HGVG and linking strategies which are based on the point-HGVG. Just as there is a close relationship between the components of the point-GVG and the rod-HGVG, there is a close relationship between the components of the point-HGVG and the higher-order edges of the rod-HGVG. We provide the construction procedures for the higher-order edges, which, like the components of the rod-HGVG, can be constructed using only sensor-provided information.

IROS Conference 2003 Conference Paper

A mobile hyper redundant mechanism for search and rescue tasks

Alon Wolf
H. Benjamin Brown
Randall W. Casciola
Albert Costa
Michael Schwerin
E. Shamas
Howie Choset

In this work we introduce a new concept of a search and rescue robotic system that is composed of an elephant trunk-like robot mounted on a mobile base. This system is capable not only of inspecting areas reachable by the mobile base but also to inspect unreachable areas such as small cracks, and pipes, using the camera mounted on its elephant trunk robot. In the report we describe the mechanical structure of the elephant trunk robot, the kinematic analysis of the structure, the robot control, and its human interface systems.

ICRA Conference 2003 Conference Paper

Accurate relative localization using odometry

Nakju Lett Doh
Howie Choset
Wan Kyun Chung

All mobile robots suffer from odometry error. Relative localization from odometry has both the systematic and the non-systematic errors. However, once a precise system error model and its parameters are given, the accuracy of odometry can be remarkably improved. Most previous works on this effort focused on the differential drive robots with little attention to the other types of mobile bases. In this paper, we analyze sources of odometry error and propose an error model for the synchro drive robot. We then describe a novel procedure to accurately estimate the error parameters of the derived error model and the covariance matrix of the synchro drive robot. However, this procedure is general for all mobile bases, so we also apply our method for the differential drive robots and show experiments. This new process uses the shape of the path, as opposed to just end points, to estimate the error parameters and covariance matrix. We happen to use the generalized Voronoi graph to generate this path. Experimental results validate the error model of the synchro drive robot and precise estimation ability of the proposed method for the synchro and the differential drive robots.

IROS Conference 2003 Conference Paper

An enhanced occupancy map for exploration via pose separation

Robert Grabowski
Pradeep K. Khosla
Howie Choset

We develop a new occupancy map that respects the role of the sensor measurement bearing and how it relates to the resolution of the existing occupancy map. We borrow an idea from Konolige for recording and tracking, in an occupancy-like map, the bearing at which sensor readings originate with respect to a given cell. Our specific contribution is in the way we process the sensor pose information, which is the bearing of the sensor readings when it indicates the presence of an obstacle in a particular cell. For each cell in the occupancy map, we calculate the greatest separation of incident poses, and then store that information in a new two-dimensional array called a pose map. A cell in the pose map measures the quality of information contained in the corresponding cell of the occupancy map. We merge the new pose map with the existing map to generate an enhanced occupancy map. Exploration plans derived from the enhanced occupancy map are more efficient and complete in that they do not guide the robot around phantom obstacles nor incorrectly classify narrow openings as closed commonly found in conventional occupancy maps.

IROS Conference 2003 Conference Paper

Autonomous exploration via regions of interest

Robert Grabowski
Pradeep K. Khosla
Howie Choset

We describe a new paradigm for exploration of unknown spaces based on maximizing the understanding of obstacles rather than the exposure of free space. We look at the interaction between multiple sensor readings and how they combine to resolve obstacles. Taking a next best view approach, we generate an inverse sensor model that identifies regions in space where a new sensor reading has maximal utility with respect to increasing the resolution of that reading. Fusion of multiple models is exploited to generate regions of interest that direct exploration in such a way as to maximize the robots understanding of its space. These techniques are applied to a team of small robots called Millibots.

IROS Conference 2003 Conference Paper

Composition of local potential functions for global robot control and navigation

David C. Conner
Alfred A. Rizzi
Howie Choset

This paper develops a method of composing simple control policies, applicable over a limited region in a dynamical system's free space, such that the resulting composition completely solves the navigation and control problem for the given system operating in a constrained environment. The resulting control policy deployment induces a global control policy that brings the system to the goal, provided that there is a single connected component of the free space containing both the start and goal configurations. In this paper, control policies for both kinematic and simple dynamical systems are developed. This work assumes that the initial velocities are somewhat aligned with the desired velocity vector field. We conclude by offering an outline of an approach for accommodating arbitrary dynamical constraints and initial conditions.

IROS Conference 2003 Conference Paper

Hierarchical simultaneous localization and mapping

Brad Lisien
Deryck Morales
David Silver 0002
George Kantor
Ioannis M. Rekleitis
Howie Choset

This paper presents a novel method of combining topological and feature-based mapping strategies to create a hierarchical approach to simultaneous localization and mapping (SLAM). More than simply running both processes in parallel, we use the topological mapping procedure to organize local feature-based methods. The result is an autonomous exploration and mapping strategy that scales well to large environments and higher dimensions while confronting the issue of obstacle avoidance. We have obtained successful results of our approach in an area spanning 5000 square meters.

IROS Conference 2003 Conference Paper

New joint design for three-dimensional hyper redundant robots

Elie A. Shammas
Alon Wolf
H. Ben Brown Jr.
Howie Choset

This paper presents a novel compact design for a two degrees of freedom (DOF) joint mechanism. The joint is optimized for compactness, strength and range of motion which makes it ideal for constructing spatial or three-dimensional hyper redundant robots. We also identify and classify various prior joint designs that led to the development of this new concept. Finally, we present the joint forward kinematics, and force and torque calculations to verify the joint's range of motion and mechanical advantage.

IROS Conference 2003 Conference Paper

Towards optimal coverage of 2-dimensional surfaces embedded in IR 3: choice of start curve

Prasad N. Atkar
Howie Choset
Alfred A. Rizzi

For automated spray painting robots, the choice of a start curve from which all subsequent paths will be determined, plays a critical role in ensuring uniform coverage of the target surface. In this paper, we ultimately propose a method to determine the start curve for two different procedures of coverage path construction. For the first procedure, we average the target surface normal to optimize the average error between desired and resultant deposition with the added goal of minimizing cycle time. For the second technique, we make recourse to the Gauss-Bonnet theorem to minimize the non-uniformity of paint deposition and cycle time for the entire coverage path.

IROS Conference 2002 Conference Paper

Development of deposition models for paint application on surfaces embedded in R 3 for use in automated path planning

David C. Conner
Prasad N. Atkar
Alfred A. Rizzi
Howie Choset

As part of an ongoing collaborative effort with the Ford Motor Company, our research aims to develop practical and efficient trajectory planning tools for automotive painting. This paper documents our efforts to develop analytic deposition models for electrostatic rotating bell (ESRB) atomizers, which have recently become widely used in the automotive painting industry. Conventional deposition models, used in earlier automatic trajectory planning tools, fail to capture the complexity of deposition patterns generated by ESRB atomizers. The models presented here take into account both the surface curvature and the deposition pattern of ESRB atomizers, enabling planning tools to optimize trajectories to meet several measures of quality, such as coating uniformity. In addition to the development of our models, we present experimental results used to evaluate our models, and verify the interaction between the deposition pattern, trajectory, and surface curvature.

ICRA Conference 2002 Conference Paper

Exploiting Critical Points to Reduce Positioning Error for Sensor-Based Navigation

Ercan U. Acar
Howie Choset

This paper presents a planner that determines a path such that the robot does not have to heavily rely on odometry to reach its goal. The planner determines a sequence of obstacle boundaries that the robot must follow to reach the goal. Since this planner is used in the context of a coverage algorithm already presented by the authors, we assume that the free space is already, completely or partially, represented by a cellular decomposition whose cell boundaries are defined by critical points of Morse functions (isolated points at obstacle boundaries). The topological relationship among the cells is represented by a graph where nodes are the critical points and edges connect the nodes that define a common cell (i. e. , the edges correspond to the cells themselves). A search of this graph yields a sequence of cells that directs the robot from a start to a goal. Once a sequence of cells and critical points are determined, a robot traverses each cell by mainly following the boundary of the cell along the obstacle boundaries and minimizes the accumulated dead-reckoning error at the intermediate critical points. This allows the robot to reach the goal robustly even in the presence of dead-reckoning error.

IROS Conference 2002 Conference Paper

Probabilistic hierarchical spatial model for mine locations and its application in robotic landmine search

Yangang Zhang
Mark J. Schervish
Howie Choset

One way to improve the efficiency of mine search, compared with a complete coverage algorithm, is to direct the search based on the spatial pattern of the minefield. This paper extends our original statistical approach (2001) to identify the regular pattern of a minefield at the beginning of the searching process. The extracted pattern parameters are used to build a probability distribution map of the configuration of the minefield. The map then can be used to guide the search for more mines efficiently. The new approach can efficiently capture the systematic and accumulated random departure of the actual mine locations from the grid pattern caused by the inaccuracy of the translational and rotational motion of the mine layer. Online implementation of our approach on a mobile robot is feasible.

ICRA Conference 2002 Conference Paper

Sensor-Based Exploration for Convex Bodies: A New Roadmap for a Convex-Shaped Robot

Ji Yeong Lee
Howie Choset

We present an algorithm that enables a convex shaped robot to explore an unknown planar workspace, i. e. , an unknown configuration space diffeomorphic to SE(2). This algorithm is based on a roadmap called the convex hierarchical generalized Voronoi graph (convex-HGVG), which is the central contribution of the paper. Since this roadmap is defined in terms of workspace distance information which is within line of sight of the convex body, we can use this roadmap to direct the robot to explore the unknown space. The challenge in defining the roadmap is that SE(2), with holes removed from it, does not have, in general, a one-dimensional retract. Therefore, we decompose the punctured SE(2) into contractible regions in which we define convex generalized Voronoi graphs (convex-GVG) and then connect these graphs with additional structures called R-edges. The convex-GVG edges and the R-edges together form the convex-HGVG. We show that the convex-HGVG is indeed a roadmap and then we demonstrate the control laws that a robot can invoke that incrementally constructs the roadmap.

ICRA Conference 2002 Conference Paper

Towards Sensor Based Coverage with Robot Teams

DeWitt Latimer IV
Siddhartha S. Srinivasa
Vincent Lee-Shue
Samuel Sonne
Howie Choset
Aaron P. Hurst

We introduce an algorithm to cover an unknown space with a homogeneous team of circular mobile robots. Our approach is based on a single robot coverage algorithm, a boustrophedon approach, which divides the target two-dimensional space into regions called cells, each of which can be covered with simple back and forth motions. Single robot coverage is then achieved by ensuring that the robot visits each cell. The new multi-robot coverage algorithm uses the same planar cell-based approach as the single robot approach, but also prescribes the methods by which multiple robots cover a cell, teams are allocated among cells, and sub-teams of robots share information in a minimalistic manner. The advantage of this method is that planning occurs in a two dimensional configuration space for a team of n robots, bypassing the need to plan in a 2n dimensional configuration space. The approach is semi-decentralized: robot teams cover the space independent of each other, but robots within a team communicate state and share information.

IROS Conference 2001 Conference Paper

Complete sensor-based coverage with extended-range detectors: a hierarchical decomposition in terms of critical points and Voronoi diagrams

Ercan U. Acar
Howie Choset
Prasad N. Atkar

Sensor-based coverage uses sensor information to determine a path that passes a detector over all points in an unknown space. Our prior work in coverage prescribed a path for a circular robot of radius r to pass over all points in unknown spaces; in this case we set the detector range /spl delta/ to be equal to the robot's radius, r. Our prior work in Voronoi diagrams prescribed a path for a circular robot with infinite detector range (/spl delta/=/spl infin/) to pass its detector over all points in an unknown bounded space. This work combines these, results to consider "efficient" coverage with a finite-range detector with r</spl delta/</spl infin/. We define a new hierarchical decomposition with two types of cells: VAST and NARROW. In the VAST-cells, we treat the circular detector like a robot and re-use our critical point based coverage algorithm. In the NARROW-cells, since the obstacles are within the detector range, we effectively have an infinite-range detector, so the robot simply follows the Voronoi diagram. This paper proves that this approach ensures complete coverage with extended-range detectors, which includes a switching procedure from VAST to NARROW-cells.

ICRA Conference 2001 Conference Paper

Exact Cellular Decomposition of Closed Orientable Surfaces Embedded in R3

Prasad N. Atkar
Howie Choset
Alfred A. Rizzi
Ercan U. Acar

We address the task of covering a closed orientable surface embedded in /spl Rfr//sup 3/ without any prior information about the surface. For applications such as paint deposition, the effector (the paint atomizer) does not explicitly cover the target surface, but instead covers an offset surface-a surface that is a fixed distance away from the target surface. Just as Canny and others use critical points to look for changes in connectivity of the free space to ensure completeness of their roadmap algorithms, we use critical points to identify changes in the connectivity of the offset surface to ensure full surface coverage. The main contribution of this work is a method to construct unknown offset surfaces using a procedure, also developed in this paper, to detect critical points.

IROS Conference 2001 Conference Paper

Limitations imposed by single DOF actuators on discrete actuator arrays

Mark Bedillion
William C. Messner
Howie Choset

The modular distributed manipulator system is an array of actuators that is capable of manipulating objects in the plane. Each actuator in the array consists of two closely spaced, orthogonally mounted motorized roller wheels whose combined action approximates a programmable vector force. The paper first derives the equations of motion for transported objects by explicitly considering the traction force from each wheel of the actuator. This contrasts with prior work, which assumed an ideal single point of contact for each actuator. A translational velocity field is developed based on these dynamics and is compared with a discrete elliptic field derived. Errors in translational dynamics under an elliptic velocity field are discussed. The paper then presents simulation results that demonstrate some of the difficulties encountered when using non-ideal actuators.

IROS Conference 2001 Conference Paper

Probabilistic methods for robotic landmine search

Yangang Zhang
Mark J. Schervish
Ercan U. Acar
Howie Choset

One way to improve the efficiency of mine search, compared with a complete coverage algorithm, is to direct the search based on the spatial distribution of the minefield. The key for the success of this probabilistic approach is to efficiently extract the spatial distribution of the minefield during the process of the search. In our research, we assume that a minefield follows a regular pattern, which belongs to a family of known patterns. A Bayesian approach to the pattern extraction is developed to extract the underlying pattern of the minefield. The algorithm performs well in its ability to catch the "actual" pattern in the situation where placement and detector errors exist, and the algorithm is efficient, therefore, online implement of the algorithm on a mobile robot is possible. Compared to the likelihood approach, the advantage of using a Bayesian approach is that this approach provides information about the uncertainty of the extracted "actual" pattern.

IROS Conference 2001 Conference Paper

Robust sensor-based coverage of unstructured environments

Ercan U. Acar
Howie Choset

Sensor-based coverage uses sensor information to determine a path that passes a detector or some effectors over all points in an unknown space. This work identifies features of a provably complete coverage algorithm to reject "bad" sensor readings in unstructured environments without performing complicated sensor-data processing. First, we briefly review our provably complete sensor-based coverage algorithm that uses an exact cellular decomposition in terms of critical points of Morse functions. Then we present features of the algorithm that are used to overcome failures due to bad sensor data. We verified our approach by performing experiments using a mobile robot that has 16 ultrasonic sensors.

ICRA Conference 2001 Conference Paper

Sensor Based Planning for Rod-Shaped Robots in Three-Dimensions: Piece-wise Retracts of R3 x S2

Ji Yeong Lee
Howie Choset
Alfred A. Rizzi

We describe a new roadmap, termed the rod-HGVG, for motion planning of a rod-shaped robot operating in a three-dimensional volume. This roadmap is defined in terms of work space distance enabling us to prescribe an incremental construction procedure. This allows the rod to explore its configuration space, R/sup 3//spl times/S/sup 2/, without ever explicitly constructing the configuration space. In fact, the rod robot need not know the work space ahead of time. We term the rod-HGVG a piecewise retract because it comprises many retracts. Homotopy theory asserts that there cannot be in general a one dimensional retract of noncontractable five-dimensional space. Instead, we define an exact cellular decomposition on R/sup 3//spl times/S/sup 2/ and a retract in each cell. Next, we "connect" the retracts of each cell forming a piecewise retract of the rod's configuration space.

ICRA Conference 2000 Conference Paper

Closed-Loop Operation of Actuator Arrays

Jonathan E. Luntz
William C. Messner
Howie Choset

An actuator array performs distributed manipulation where an object being transported and manipulated rests on a large number of stationary supporting actuators. The authors have developed a macroscopic actuator array consisting of many motorized wheels. As opposed to a MEMS array, the analysis requires the explicit modeling of the discreteness in the system, including the set of supports, distribution of weight, and generation of traction forces. Using an open-loop wheel velocity field, discreteness causes undesirable behavior such as unstable rotational equilibria, suggesting the use of object feedback. Discrete distributed control algorithms are derived by inverting the dynamics of manipulation. These algorithms reduce the many-input-three-output control problem to a three-input-three-output control problem.

ICRA Conference 2000 Conference Paper

Critical Point Sensing in Unknown Environments

Ercan U. Acar
Howie Choset

Many motion planning algorithms use Morse functions to characterize the free space. Specifically, these algorithms look at the critical points of a Morse function to denote the topological changes in the free space. This paper introduces methods to sense critical points and ensure all critical points are "seen" by a coverage algorithm. Experimental results performed on a mobile robot are also presented.

ICRA Conference 2000 Conference Paper

Exact Cellular Decompositions in Terms of Critical Points of Morse Functions

Howie Choset
Ercan U. Acar
Alfred A. Rizzi
Jonathan E. Luntz

Exact cellular decompositions are structures that globally encode the topology of a robot's free space, while locally describing the free space geometry. These structures have been widely used for path planning between two points, but can be used for mapping and coverage of robot free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. In this paper, we derive a general framework for defining decompositions in terms of critical points and then give examples, each corresponding to a different task. All of the results in this paper are derived in an m-dimensional Euclidean space, but the examples depicted in the figures are 2D and 3D for ease of presentation.

ICRA Conference 1999 Conference Paper

Discrete Actuator Array Vectorfield Design for Distributed Manipulation

Jonathan E. Luntz
William C. Messner
Howie Choset

The modular distributed manipulator system (MDMS) is a macroscopic actuator array which can manipulate objects in the plane. The piecewise-constant dynamics of manipulation on the MDMS are developed based on an exact discrete representation of the system. The resulting dynamics are inverted enabling the calculation of an open-loop vectorfield which provides arbitrary uniform object dynamics. The vector field positions, and under certain assumptions, orients objects.

ICRA Conference 1999 Conference Paper

Open-Loop Orientability of Objects on Actuator Arrays

Jonathan E. Luntz
William C. Messner
Howie Choset

An actuator array is a form of distributed manipulation where an object being transported and manipulated rests on a large number of supporting actuators. On a discrete array employing an open-loop field, some size and shape objects may have unstable equilibria due to this discreteness. The functional relationship between object dimensions relative to array spacing and rotational stability is examined, and a map of this function is generated. The geometry behind this relationship is also examined, and analytical expressions for the boundaries between stable and unstable regions in the map are derived.

ICRA Conference 1999 Conference Paper

Path Planning and Control for AERCam, a Free-Flying Inspection Robot in Space

Howie Choset
Ross A. Knepper
Joleen Flasher
Sean Walker
Andrew Alford
Dean Jackson
David Kortenkamp
Jaime J. Fernandez

This paper describes a prototype robot and the necessary path planning and control for space inspection applications. The robot is the first generation of a free-flying robotic camera that will assist astronauts in constructing and maintaining the Space Station. The robot will provide remote views to astronauts inside the Space Shuttle and future Space Station, and to ground controllers. The paper describes a planar robot prototype autonomously moving about an air bearing table, and introduces a method for determining paths in three-dimensions for efficient fuel use. Finally, the paper describes the software simulation of the path planner with the future Space Station.

AAAI Conference 1999 Conference Paper

Sensor Based Coverage of Unknown Environment for Land Mine Detection

Ercan Acar
Morgan Simmons
Michael Rosenblatt
Maayan Roth
Mary Berna
Yonatan Mittlefehldt
Howie Choset
Carnegie Mellon University

This paper introduces a sensor based coverage algorithm and an overview of a mobile robot system for demining. The algorithm is formulated in terms of critical points which are the points where the topology of an environment changes. We developed a provably complete coverage algorithm which makes a robot pass over all possible points of an unknown environment.

ICRA Conference 1999 Conference Paper

The Arc-Transversal Median Algorithm: An Approach to Increasing Ultrasonic Sensor Accuracy

Keiji Nagatani
Howie Choset
Nicole A. Lazar

This paper describes a new method for determining range information about a robot's surroundings using low resolution ultrasonic sensors. These sensors emit ultrasound which bounces off of nearby objects and returns to the sensor. The time-of-flight for the sound to return to the sensor is the distance between the sensor and the object. A sonar arc represents the possible locations of the object. We model these locations with a simple uniform probability distribution on the sonar arc. We then introduce a new method to fuse sonar data to determine the actual obstacle location. This new method is termed the arc-transversal median method because the robot determines the location of an object by intersecting one arc with other arcs whose angle-of-intersection exceeds a threshold and then taking the median of the intersection. The median is a robust estimator that is insensitive to noise because a few stray readings will not affect the median. We show via some simple geometric relationships, that this method can improve the accuracy of the sonar sensor by a specified amount, when certain assumptions were in place. Finally, experimental results on a real mobile robot verify this approach.

IROS Conference 1999 Conference Paper

Toward robust sensor based exploration by constructing reduced generalized Voronoi graph

Keiji Nagatani
Howie Choset

Considers sensor based mobile robot exploration in an unknown indoor environment. One of the big problems in this area is positioning error. To deal with this problem in the exploration task, we proposed a localization method using a partially constructed topological map termed the generalized Voronoi graph (GVG). The GVG-based method performed successfully in some large scale indoor environments, but had problems resulting from poor sensing ability of the sixteen sonar sensors on-board the robot. The poor sensing ability was particularly deleterious at geometric structures in the GVG that were "unstable. " To solve the problem, we adopted "the Reduced Generalized Voronoi Graph (RGVG)" for the exploration map instead of the original GVG. The RGVG is a stable subset of the GVG and is sufficient for motion planning. To enable realistic and reliable exploration using the RGVG structure, we developed an edge matching procedure for topology matching. In this paper, we introduce the RGVG structure and the edge matching procedure for robust exploration. Experimental results verify the described work.

ICRA Conference 1998 Conference Paper

Towards Exact Localization without Explicit Localization with the Generalized Voronoi Graph

Keiji Nagatani
Howie Choset
Sebastian Thrun

Sensor based exploration is a task which enables a robot to explore and map an unknown environment, using sensor information. The map used in this paper is the generalized Voronoi graph (GVG). The robot explores an unknown environment using an already developed incremental construction procedure to generate the GVG using sensor information. This paper presents some initial results which uses the GVG for robot localization, while mitigating the need to update encoder values. Experimental results verify the described work.

IROS Conference 1997 Conference Paper

Mobile robot navigation: implementing the GVG in the presence of sharp corners

E. Ilhan Konukseven
Howie Choset

A robot can explore an unknown environment by incrementally constructing a roadmap of that environment using line of sight sensor information. Recall that a roadmap is a one-dimensional representation of a robot's environment. This paper addresses one problem that occurs while generating a roadmap: what happens when sonar sensors cannot detect sharp objects because of the specularities? To do this, a new sensor model is combined with an already existing incremental construction procedure for a roadmap. Experiments on a mobile robot validate the results of this paper. A generalised Voronoi graph is used.

ICRA Conference 1997 Conference Paper

Parcel manipulation and dynamics with a distributed actuator array: the virtual vehicle

Jonathan E. Luntz
William C. Messner
Howie Choset

We are developing a materials handling system where many small simple actuators cooperate to transport and to manipulate large objects in the plane. A discrete set of cells, each comprising two actuators, are fixed in a planar array. By coordinating the actuators in the cells on which an object rests, an object can be transported and manipulated. In essence, this system is an improvement over traditional conveyor systems in that objects can be re-oriented, as well as conveyed. Such an array provides flexible materials handling in which many objects independently can be manipulated and transported at the same time. The array is coordinated in a distributed manner where each cell has its own controller and each controller communicates with its neighbors. Towards the goal of motion planning, in this paper we consider the dynamics of parcel transport and manipulation. The parcel dynamics are based on an exact discrete representation of the system, unlike other methods where a continuity assumption is made. Two types of contact models are considered.

ICRA Conference 1997 Conference Paper

Sensor based planning for a planar rod robot: incremental construction of the planar rod-HGVG

Howie Choset
Brian Mirtich
Joel W. Burdick

This work considers sensor based motion planning for rod-shaped robots in unknown environments. The motion planning scheme is based on the rod hierarchical generalized Voronoi graph (rod-HGVG). The rod-HGVG is a roadmap for rod-like robots, and is an extension of a prior roadmap for point-like robots. We give an incremental method to construct the rod-HGVG thereby enabling exploration of unknown environments. An important practical feature of the algorithm is its sole reliance upon the use of work space distance measurements to objects that are within line of sight. Such measurements can be readily provided by conventional range sensors. Moreover, motion planning in a configuration space is achieved without explicitly constructing each configuration space obstacle. A key result derived in this paper is the distance gradient between two convex sets.

ICRA Conference 1996 Conference Paper

Sensor based planning for a planar rod robot

Howie Choset
Joel W. Burdick

Sensor based planning for rod-shaped robots is necessary for the realistic deployment of noncircular symmetric robots into unknown environments. To this end, the rod hierarchical generalized Voronoi graph (rod-HGVG), introduced in this paper, is a roadmap for rod-like robots. A key feature of this roadmap is that it can be incrementally constructed using distance (range) information. This planning paradigm is an extension of previous work on sensor based planning for point robots.

ICRA Conference 1995 Conference Paper

Sensor Based Planing, Part I: The Generalized Voronoi Graph

Howie Choset
Joel W. Burdick

This paper prescribes an incremental procedure to construct the generalized Voronoi graph (GVG) and the hierarchical generalized Voronoi graph (HGVG) detailed in the companion paper. The procedure requires only local distance sensor measurements, and therefore the method can be used as a basis for sensor based planning algorithms.

ICRA Conference 1995 Conference Paper

Sensor Based Planing, Part II: Incremental COnstruction of the Generalized Voronoi Graph

Howie Choset
Joel W. Burdick

This paper introduces a 1-dimensional network of curves termed the generalized Voronoi graph (GVG) and its extension, the hierarchical generalized Voronoi graph (HGVG), which can be used as a basis for a roadmap or retract-like structure. The GVG and HGVG provide a basis for sensor based path planning in an unknown static environment. In this paper, the GVG and HGVG are defined and some of their properties are exploited to show their utility for motion planning. A companion paper describes how to use the GVG and HGVG for the purposes of sensor based planning.

ICRA Conference 1994 Conference Paper

Sensor-Based Planning and Nonsmooth Analysis

Howie Choset
Joel W. Burdick

This paper describes some initial steps towards sensor based path planning in an unknown static environment. The method is a based on a sensor-based incremental construction of a one-dimensional retract of the free space. In this paper we introduce a retract termed the generalized Voronoi graph, and also analyze the roadmap of Canny and Lin's opportunistic path planner (1990, 1993). The bulk of this paper is devoted to the application of nonsmooth analysis to the Euclidean distance function. We show that the distance function is in fact nonsmooth at the points which are required to construct the plan. This analysis leads directly to the incorporation of simple and realistic sensor models into the planning scheme. >

IROS Conference 1993 Conference Paper

Simulated and experimental results of dual resolution sensor based planning for hyper-redundant manipulators

Nobuaki Takanashi
Howie Choset
Joel W. Burdick

This paper presents a dual-resolution local sensor based planning method for hyper-redundant robot mechanisms. Two classes of sensor feedback control methods, working at different sampling rates and different spatial resolutions, are considered: full shape modification (FSM), and partial shape modification (PSM). FSM and PSM cooperate to utilize a mechanism's hyper-redundancy to enable both local obstacle avoidance and end-effector placement in real-time. These methods have been implemented on a thirty degree of freedom hyper-redundant manipulator which has 11 ultrasonic distance measurement sensors and 20 infrared proximity sensors. The implementation of these algorithms in a dual CPU real-time control computer, an innovative sensor bus architecture, and a novel graphical control interface are described. Experimental results obtained using this test bed show the efficacy of the proposed method.