The integration of large language models (LLMs) into robotic task planning has unlocked better reasoning capabilities for complex, long-horizon workflows. However, ensuring safety in LLM-driven plans remains a critical challenge, as these models often prioritize task completion over risk mitigation. This paper introduces SAFER (Safety-Aware Framework for Execution in Robotics), a multi-LLM framework designed to embed safety awareness into robotic task planning. SAFER employs a Safety Agent that operates alongside the primary task planner, providing safety feedback. Additionally, we introduce LLM-as-a-Judge, a novel metric leveraging LLMs as evaluators to quantify safety violations within generated task plans. Our framework integrates safety feedback at multiple stages of execution, enabling real-time risk assessment, proactive error correction, and transparent safety evaluation. We also integrate a control framework using Control Barrier Functions (CBFs) to ensure safety guarantees within SAFER’s task planning. We evaluated SAFER against state-of-the-art LLM planners on complex long-horizon tasks involving heterogeneous robotic agents, demonstrating its effectiveness in reducing safety violations while maintaining task efficiency. We also verify the task planner and safety planner through actual hardware experiments involving multiple robots and a human.

Trajectory retiming is the task of computing a feasible time parameterization to traverse a path. It is commonly used in the decoupled approach to trajectory optimization whereby a path is first found, then a retiming algorithm computes a speed profile that satisfies kino-dynamic and other constraints. While trajectory retiming is most often formulated with the minimum-time objective (i.e. traverse the path as fast as possible), it is not always the most desirable objective, particularly when we seek to balance multiple objectives or when bang-bang control is unsuitable. In this paper, we present a novel algorithm based on factor graph variable elimination that can solve for the global optimum of the retiming problem with quadratic objectives as well (e.g. minimize control effort or match a nominal speed by minimizing squared error), which may extend to arbitrary objectives with iteration. Our work extends prior works, which find only solutions on the boundary of the feasible region, while maintaining the same linear time complexity from a single forward-backward pass. We experimentally demonstrate that (1) we achieve better real-world robot performance by using quadratic objectives in place of the minimum-time objective, and (2) our implementation is comparable or faster than state-of-the-art retiming algorithms.

Despite the increasing adoption of Deep Reinforcement Learning (DRL) for Autonomous Surface Vehicles (ASVs), there still remain challenges limiting real-world deployment. In this paper, we first integrate buoyancy and hydrodynamics models into a modern Reinforcement Learning framework to reduce training time. Next, we show how system identification coupled with domain randomization improves the RL agent performance and narrows the sim-to-real gap. Real-world experiments for the task of capturing floating waste show that our approach lowers energy consumption by 13.1% while reducing task completion time by 7.4%. These findings, supported by sharing our open-source implementation, hold the potential to impact the efficiency and versatility of ASVs, contributing to environmental conservation efforts.

Robot art presents an opportunity to both showcase and advance state-of-the-art robotics through the challenging task of creating art. Creating large-scale artworks in particular engages the public in a way that small-scale works cannot, and the distinct qualities of brush strokes contribute to an organic and human-like quality. Combining the large scale of murals with the strokes of the brush medium presents an especially impactful result, but also introduces unique challenges in maintaining precise, dextrous motion control of the brush across such a large workspace. In this work, we present the first robot to our knowledge that can paint architectural-scale murals with a brush. We create a hybrid robot consisting of a cable-driven parallel robot and 4 degree of freedom (DoF) serial manipulator to paint a 27m by 3.7m mural on windows spanning 2-stories of a building. We discuss our approach to achieving both the scale and accuracy required for brush-painting a mural through a combination of novel mechanical design elements, coordinated planning and control, and on-site calibration algorithms with experimental validations.

To enable a mobile manipulator to effectively maneuver a cart, we derive a dynamic model for the cart that incorporates the nonholonomic constraints on its motion, and use this model to formulate an estimator for the cart's inertial parameters. By deriving the dynamic equations of the cart using a constrained Euler-Lagrange formulation, we are able to directly incorporate nonholonomic constraints into the dynamics in a way that is independent of the kinematic parameters of the cart (e.g., specific wheel configuration, wheel radius, etc.), eliminating the need to either calibrate or estimate these kinematic parameters. We then construct an extended Kalman filter (including an explicit calculation of the linearized system and observation matrices) that uses an augmented state representation to estimate the cart's inertial parameters. We validate our approach both in simulation and experimentally using a mobile manipulator to maneuver a typical shopping cart. These experiments confirm the accuracy of our estimator, show that accurate estimation of the inertial parameters can significantly reduce the force/torque needed to successfully control the system, and illuminate the effects of varying the contact points at which the mobile manipulator applies forces and torques to guide the cart along a desired trajectory.

Sampling-based algorithms solve the path planning problem by generating random samples in the searchspace and incrementally growing a connectivity graph or a tree. Conventionally, the sampling strategy used in these algorithms is biased towards exploration to acquire information about the search-space. In contrast, this work proposes an optimization-based procedure that generates new samples so as to improve the cost-to-come value of vertices in a given neighborhood. The application of the proposed algorithm adds an exploitativebias to sampling and results in a faster convergence to the optimal solution compared to other state-of-the-art sampling techniques. This is demonstrated using benchmarking experiments performed for 7 DOF Panda and 14 DOF Baxter robots.

This work focuses on the capability of Mobile Manipulators to effectively control and maneuver cart-like non-holonomic systems. These cart-like systems are passive-wheeled objects with nonholonomic constraints with varying inertial parameters. We derive the dynamic equations of the cart-like system using a constrained Euler-Lagrange formulation and propose a Linear Quadratic Regulator controller to move the cart along a desired trajectory using external forces (applied by the MM) at a given contact point. For the MM, we present a control architecture to i) control the mobile base to keep the cart inside the workspace of the manipulator and ii) a control Lyapunov function formulation to control the manipulator in torque control, while decoupling the motion of the base from the arm and applying the required wrench onto the object. We validate our approach experimentally, using a MM to push a shopping cart and track desired trajectories. These experiments show the accuracy of the control architecture to track the desired trajectories for carts with different inertial parameters and improve the controllability of the system by changing the contact point on the cart.

Effective coordination of heterogeneous multi-robot teams requires optimizing allocations, schedules, and motion plans in order to satisfy complex multi-dimensional task requirements. This challenge is exacerbated by the fact that real-world applications inevitably introduce uncertainties into robot capabilities and task requirements. In this paper, we extend our previous work on trait-based time-extended task allocation to account for such uncertainties. Specifically, we leverage the Sequential Probability Ratio Test to develop an algorithm that can guarantee that the probability of failing to satisfy task requirements is below a user-specified threshold. We also improve upon our prior approach by accounting for temporal deadlines in addition to synchronization and precedence constraints in a Mixed-Integer Linear Programming model. We evaluate our approach by benchmarking it against three baselines in a simulated battle domain in a city environment and compare its performance against a state-of-the-art framework in a pandemic-inspired multi-robot service coordination problem. Results demonstrate the effectiveness and advantages of our approach, which leverages redundancies to manage risk while simultaneously minimizing makespan.

Systematically designing local interaction rules to achieve collective behaviors in robot swarms is a challenging endeavor, especially in micro robots, where size restrictions imply severe sensing, communication, and computation limitations. In such robot swarms, performing useful functions is often preconditioned on the formation of high-density aggregations which can facilitate collective signaling and information sharing. In this article, we present a systematic approach to control aggregation behaviors by leveraging the physical interactions in a swarm of 300 3-mm vibration-driven micro bristle robots that we designed and fabricated. We demonstrate the ability to control the degree of aggregation by varying the motility characteristics of the robots through global vibration frequency and amplitude inputs, after comprehensive characterization, modeling, and simulation of the locomotion dynamics and robot interactions. To quantify the degree of aggregation, we also introduce a new metric, the motility-induced phase separation index index, which unlike many existing methods does not require a scenario-specific tuning of parameters. Our investigations reveal how physics-driven interaction mechanisms can be exploited to achieve desired behaviors in minimally equipped robot swarms and highlight the specific ways in which hardware and software developments aid in the achievement of collision-induced aggregations.

This study proposes a hierarchically integrated framework for safe task and motion planning (TAMP) of bipedal locomotion in a partially observable environment with dynamic obstacles and uneven terrain. The high-level task planner employs linear temporal logic for a reactive game synthesis between the robot and its environment and provides a formal guarantee on navigation safety and task completion. To address environmental partial observability, a belief abstraction model is designed by partitioning the environment into multiple belief regions and employed at the high-level navigation planner to estimate the dynamic obstacles' location. This additional location information of dynamic obstacles offered by belief abstraction enables less conservative long-horizon navigation actions beyond guaranteeing immediate collision avoidance. Accordingly, a synthesized action planner sends a set of locomotion actions to the middle-level motion planner while incorporating safe locomotion specifications extracted from safety theorems based on a reduced-order model (ROM) of the locomotion process. The motion planner employs the ROM to design safety criteria and a sampling algorithm to generate nonperiodic motion plans that accurately track high-level actions. At the low level, a foot placement controller based on an angular-momentum linear inverted pendulum model is implemented and integrated with an ankle-actuated passivity-based controller for full-body trajectory tracking. To address external perturbations, this study also investigates the safe sequential composition of the keyframe locomotion state and achieves robust transitions against external perturbations through reachability analysis. The overall TAMP framework is validated with extensive simulations and hardware experiments on bipedal walking robots Cassie and Digit designed by Agility Robotics.

We present GTGraffiti, a graffiti painting system from Georgia Tech that tackles challenges in art, hardware, and human-robot collaboration. The problem of painting graffiti in a human style is particularly challenging and requires a system-level approach because the robotics and art must be designed around each other. The robot must be highly dynamic over a large workspace while the artist must work within the robot's limitations. Our approach consists of three stages: artwork capture, robot hardware, and planning & control. We use motion capture to capture collaborator painting motions which are then composed and processed into a time-varying linear feedback controller for a cable-driven parallel robot (CDPR) to execute. In this work, we will describe the capturing process, the design and construction of a purpose-built CDPR, and the software for turning an artist's vision into control commands. Our work represents an important step towards faithfully recreating human graffiti artwork by demonstrating that we can reproduce artist motions up to 2m/s and 20m/s2within 9.3mm RMSE to paint artworks.

This paper presents a real-time control framework for consensus in operational space for robotic manipulators while satisfying task and input constraints. Consensus in operational space, as compared to joint space, enables heterogeneous robotic manipulators to achieve consensus. However, traditional frameworks tend to ignore task and input constraints while achieving consensus in operational space. We address this problem by defining safe sets in operational space and then ensure task constraint by designing Control Barrier Functions (CBF) in operational space. Control barrier functions guarantees to provide collision-free behavior for the robotic manipulator by modifying the nominal controller in a minimally invasive manner such that the trajectory of the manipulator remains in the safe set. The Quadratic Programming (QP) formulation also ensures that the nominal controller is only modified when the constraints are active, and the resulting controller is optimal in a min-norm setting. Our approach contrasts the traditional potential field method, which continues to influence the nominal controller because of its attractive and repulsive field design, and is therefore unsuitable for consensus problems. We also incorporate the input constraint in our QP formulation to ensure that the resulting controller complies with the task and input constraints. We show the efficacy of the proposed approach on 7 Degree of Freedom (DoF) KUKA LBR iiwa, 6 DoF KUKA KR5 R650 and 7 DoF Flexiv Rizon robotic manipulators, each with different dynamical and kinematic models using Dynamic Animation and Robotics Toolkit (DART) physics engine.

We present a locally optimal tracking controller for Cable Driven Parallel Robot (CDPR) control based on a time-varying Linear Quadratic Gaussian (TV-LQG) controller. In contrast to many methods which use fixed feedback gains, our time-varying controller computes the optimal gains depending on the location in the workspace and the future trajectory. Meanwhile, we rely heavily on offline computation to reduce the burden of online implementation and feasibility checking. Following the growing popularity of probabilistic graphical models for optimal control, we use factor graphs as a tool to formulate our controller for their efficiency, intuitiveness, and modularity. The topology of a factor graph encodes the relevant structural properties of equations in a way that facilitates insight and efficient computation using sparse linear algebra solvers. We first use factor graph optimization to compute a nominal trajectory, then linearize the graph and apply variable elimination to compute the locally optimal, time varying linear feedback gains. Next, we leverage the factor graph formulation to compute the locally optimal, time-varying Kalman Filter gains, and finally combine the locally optimal linear control and estimation laws to form a TV-LQG controller. We compare the tracking accuracy of our TV-LQG controller to a state-of-the-art dual-space feed-forward controller on a 2.9m x 2.3m, 4-cable planar robot and demonstrate improved tracking accuracies of 0.8° and 11.6 mm root mean square error in rotation and translation respectively.

In the context of heterogeneous multirobot teams deployed for executing multiple tasks, this article develops an energy-aware framework for allocating tasks to robots in an online fashion. With a primary focus on long-duration autonomy applications, we opt for a survivability-focused approach. Toward this end, the task prioritization and execution—through which the allocation of tasks to robots is effectively realized—are encoded as constraints within an optimization problem aimed at minimizing the energy consumed by the robots at each point in time. In this context, an allocation is interpreted as a prioritization of a task over all others by each of the robots. Furthermore, we present a novel framework to represent the heterogeneous capabilities of the robots, by distinguishing between the features available on the robots and the capabilities enabled by these features. By embedding these descriptions within the optimization problem, we make the framework resilient to situations, where environmental conditions make certain features unsuitable to support a capability and when component failures on the robots occur. We demonstrate the efficacy and resilience of the proposed approach in a variety of use-case scenarios, consisting of simulations and real robot experiments.

In this paper, we study the problem of dynamic interaction between a robot and an unknown object (e.g., catching a ball, or handing off an object during locomotion). In particular, we propose a method for estimating the inertial parameters of an object during dynamic interaction, while minimally altering the trajectory of the object – a minimal interaction approach. Our method combines trajectory estimation (e.g., using standard methods from computer vision) with a model-based estimator that exploits the robot’s known dynamic model. We first develop the method for a generalized three-dimensional problem, and then evaluate the method for the case of an object moving along a linear trajectory. We present experimental results obtained using a KUKA iiwa 7 interacting with rolling balls of varying mass. Our experiments demonstrate that the mass of the objects can be accurately estimated at the moment of impact when accurate object trajectory estimates are available, and that significant improvement can be obtained by incorporating force measurements at the contact point while following the object.

Interest in soft continuum arms has increased as their inherent material elasticity enables safe and adaptive interactions with the environment. However to achieve full autonomy in these arms, accurate three-dimensional shape sensing is needed. Vision-based solutions have been found to be effective in estimating the shape of soft continuum arms. In this paper, a vision-based shape estimator that utilizes a geometric strain based representation for the soft continuum arm’s shape, is proposed. This representation reduces the dimension of the curved shape to a finite set of strain basis functions, thereby allowing for efficient optimization for the shape that best fits the observed image. Experimental results demonstrate the effectiveness of the proposed approach in estimating the end effector with accuracy less than the soft arm’s radius. Multiple basis functions are also analyzed and compared for the specific soft continuum arm in use.

Cooperative manipulation systems inherently cause internal stress on the common object. Many works have proposed methods to eliminate this internal stress. However, in this paper, we show that this property can be cautiously leveraged to compensate for external disturbance on the cooperative system, particularly disturbances that occur due to collision along the links of one of the cooperating robots. We present an impedance-based scheme to control the level of compensation, thereby regulating the internal stress on the object due to the applied compensation wrenches. Previously, we introduced a method to compensate for collision with one arm of the system, but that approach sometimes caused untenable stress on the object. With the impedance-based compensation strategy presented in this paper, a suitable trade-off between maintaining the desired pose of the grasped object and limiting the permissible internal stress on the object, is achieved. We demonstrate our approach by using two kuka arms to cooperatively grasp and lift a rod in simulation.

This paper presents a real-time safety and control for robot manipulators using control barrier functions and control Lyapunov functions in operational space. We first define the operational space in terms of system dynamics, jacobian, and torques and then ensure safety by designing Control Barrier Functions (CBF) around the body links of the robotic manipulator. The control barrier function provides provable collision-free behavior for the robotic manipulator by modifying the nominal control in a minimally invasive manner to formally satisfy the safety constraints. CBFs are formulated as a quadratic programming problem, which can be solved in real-time. We also design a controller based on Rapidly Exponentially Stabilizing Control Lyapunov Function (RESCLF) and quadratic programming to meet multiple objectives while ensuring exponential convergence. We then extend our formulation to solve RESCLF and CBF in a unified formulation to design the controller while ensuring the safety of manipulators and guaranteeing the torque saturation. The efficacy of the proposed approach is shown on 7 Degree of Freedom (DoF) KUKA LBR iiwa robot using Dynamic Animation and Robotics Toolkit (DART) physics engine.

To realize effective heterogeneous multi-robot teams, researchers must leverage individual robots’ relative strengths and coordinate their individual behaviors. Specifically, heterogeneous multi-robot systems must answer three important questions: who (task allocation), when (scheduling), and how (motion planning). While specific variants of each of these problems are known to be NP-Hard, their interdependence only exacerbates the challenges involved in solving them together. In this paper, we present a novel framework that interleaves task allocation, scheduling, and motion planning. We introduce a search-based approach for trait-based time-extended task allocation named Incremental Task Allocation Graph Search (ITAGS). In contrast to approaches that solve the three problems in sequence, ITAGS’s interleaved approach enables efficient search for allocations while simultaneously satisfying scheduling constraints and accounting for the time taken to execute motion plans. To enable effective interleaving, we develop a convex combination of two search heuristics that optimizes the satisfaction of task requirements as well as the makespan of the associated schedule. We demonstrate the efficacy of ITAGS using detailed ablation studies and comparisons against two state-of-the-art algorithms in a simulated emergency response domain.

This Workshop on the Algorithmic Foundations of Robotics (WAFR) Special Issue of the IEEE Transactions on Automation Science and Engineering (T-ASE) brings together eight extended articles from the thirteenth WAFR. While these eight articles span several application domains, they demonstrate advances in automation through algorithmic development and analysis. Nomination to this Special Issue was done in coordination with the entire program committee and guest edited by the four WAFR Co-Chairs. The articles in this Special Issue highlight cutting-edge research in general tools for motion planning, learning, control, manipulation, sensor-based planning, and robotic design.

Riemannian Motion Policies (RMPs) have recently been introduced as a way to specify second-order motion policies defined on robot task spaces. RMP-based approaches have the advantage of being more general than traditional approaches based on operational space control; for example, the generalized task inertia in an RMP can be fully state-dependent, which is particularly effective in designing collision avoidance bahaviors. But until now RMPs have been applied only to fully actuated systems, i.e. systems for which each degree of freedom (DoF) can be directly actuated by a control input. In this paper, we present a method that extends the RMP formalism to a class of underacutated systems whose dynamics are amenable to a decomposition into a fully-actuated subsystem and a residual dynamics. We show the efficacy of the approach by constructing a suitable decomposition for a Wheeled-Inverted-Pendulum (WIP) humanoid robot and applying our method to derive motion policies for combined locomotion and manipulation tasks. Simulation results are presented for a 7-DoF system with one degree of underactuation.

Cooperative manipulation offers many advantages over single-arm manipulation. However, this comes at a cost of added complexity, both in modeling and control of multi-arm systems. Much research has been focused on determining optimal load distribution strategies based on several objective functions, some of which include manipulability, energy consumption and joint torque minimization. This paper presents an internal loading strategy that is subject to the estimate of the external disturbances along the body of one or more of the arms involved in the manipulation process. The authors of this paper propose a reaction strategy to external disturbances by transforming the disturbance forces into internal forces on the object through appropriate load distribution on the cooperative arms. The goal is to have a set-point on the object, track a given trajectory while compensating for external disturbances along the links of some of the robot arms involved in the cooperative manipulation.

We present a hierarchical framework for trajectory optimization and optimal feedback whole-body control of wheeled inverted pendulum (WIP) humanoid robot. The framework extends rapidly exponentially stabilizing control Lyapunov functions (RES-CLF) to operational space for controlling WIP humanoid robots while utilizing a hierarchical framework to compute an optimal policy. The upper level of the hierarchy encodes locomotion tasks, while the lower level incorporates the full system dynamics, including manipulation tasks to be performed. The framework computes an optimal policy directly in the operational space. Thus it avoids computing inverse kinematics or inverse dynamics explicitly. The framework can handle torque and task constraints while guaranteeing exponential convergence and min-norm control from RES-CLF. The efficacy of the framework is demonstrated on 18 degrees of freedom (DoF) WIP humanoid robot, Golem Krang, and 7 DoF planar WIP humanoid robot.

Chinese calligraphy is a unique art form with great artistic value but difficult to master. In this paper, we formulate the calligraphy writing problem as a trajectory optimization problem, and propose an improved virtual brush model for simulating the real writing process. Our approach is inspired by pseudospectral optimal control in that we parameterize the actuator trajectory for each stroke as a Chebyshev polynomial. The proposed dynamic virtual brush model plays a key role in formulating the objective function to be optimized. Our approach shows excellent performance in drawing aesthetically pleasing characters, and does so much more efficiently than previous work, opening up the possibility to achieve real-time closed-loop control.

In this paper we consider a constrained coverage control problem for a team of mobile robots. The robots are asked to provide sensor coverage over a two-dimensional domain, while being constrained to only move on a curve. The unconstrained coverage problem can be effectively solved by defining a locational cost to be minimized by the robots, in a decentralized fashion, using gradient descent. However, a direct projection of the solution to the unconstrained problem onto the curve may result in a very poor spatial allocation of the team within the two-dimensional domain. Therefore, we propose a modification to the locational cost, which incorporates the constraints, and a convex relaxation that allows us to efficiently minimize a convex approximation of the cost using a decentralized strategy. The resulting algorithm is implemented on a team of mobile robots.

In this paper, we present a whole-body control framework for Wheeled Inverted Pendulum (WIP) Humanoids. WIP Humanoids are redundant manipulators dynamically balancing themselves on wheels. Characterized by several degrees of freedom, they have the ability to perform several tasks simultaneously, such as balancing, maintaining a body pose, controlling the gaze, lifting a load or maintaining end-effector configuration in operation space. The problem of whole-body control is to enable simultaneous performance of these tasks with optimal participation of all degrees of freedom at specified priorities for each objective. The control also has to obey constraint of angle and torque limits on each joint. The proposed approach is hierarchical with a low level controller for body joints manipulation and a high-level controller that defines center of mass (CoM) targets for the low-level controller to control zero dynamics of the system driving the wheels. The low-level controller plans for shorter horizons while considering more complete dynamics of the system, while the high-level controller plans for longer horizon based on an approximate model of the robot for computational efficiency.

Planning flight trajectories is important for practical application of flying systems. This topic has been well studied for fixed and rotary winged aerial vehicles, but far fewer works have explored it for flapping systems. Bat Bot (B2) is a bio-inspired flying robot that mimics bat flight, and it possesses the ability to follow a designed trajectory with its on-board electronics and sensing. However, B2's periodic flapping and its complex aerodynamics present major challenges in modeling and planning feasible flight paths. In this paper, we present a generalized approach that uses a model with direct collocation methods to plan dynamically feasible flight maneuvers. The model is made to be both accurate through collection of load cell force data for parameter selection and computationally inexpensive such that it can be used efficiently in a nonlinear solver. We compute the trajectory of launching B2 to a desired altitude and a banked turn maneuver, and we validate our methods with experimental flight results of tracking the launch trajectory with a PD controller.

In robot swarms operating under highly restrictive sensing and communication constraints, individuals may need to use direct physical proximity to facilitate information exchange. However, in certain task-related scenarios, this requirement might conflict with the need for robots to spread out in the environment, e.g., for distributed sensing or surveillance applications. This paper demonstrates how a swarm of minimally-equipped robots can form high-density robot aggregates that coexist with lower robot densities in space. We envision a scenario where a swarm of vibration-driven robots-which sit atop bristles and achieve directed motion by vibrating them-move randomly in an environment while colliding with each other. Theoretical techniques from the study of far-from-equilibrium collectives and statistical mechanics clarify the mechanisms underlying the formation of these high and low density regions. Specifically, we capitalize on a transformation that connects the collective properties of a system of self-propelled particles with that of a well-studied molecular fluid system, thereby inheriting the rich theory of equilibrium thermodynamics. Real robot experiments as well as simulations illustrate how inter-robot collisions can precipitate the formation of non-uniform robot densities in a closed and bounded region.

In this paper we present a study of a specific class of vibration-driven robots: the brushbots. In a bottom-up fashion, we start by deriving dynamic models of the brushes and we discuss the conditions under which these models can be employed to describe the motion of brushbots. Then, we present two designs of brushbots: a fully-actuated platform and a differential-drive-like one. The former is employed to experimentally validate both the developed theoretical models and the devised motion control algorithms. Finally, a coordinated-control algorithm is implemented on a swarm of differential-drive-like brushbots in order to demonstrate the design simplicity and robustness that can be achieved by employing a vibration-based locomotion strategy.

Bats are unique in that they can achieve unrivaled agile maneuvers due to their functionally versatile wing conformations. Among these maneuvers, roosting (landing) has captured attentions because bats perform this acrobatic maneuver with a great composure. This work attempts to reconstruct bat landing maneuvers with a Micro Aerial Vehicle (MAV) called Allice. Allice is capable of adjusting the position of its Center of Gravity (CG) with respect to the Center of Pressure (CP) using a nonlinear closed-loop feedback. This nonlinear control law, which is based on the method of input-output feedback linearization, enables attitude regulations through variations in CG-CP distance. To design the model-based nonlinear controller, the Newton-Euler dynamic model of the robot is considered, in which the aerodynamic coefficients of lift and drag are obtained experimentally. The performance of the proposed control architecture is validated by conducting several experiments.

In this paper, we propose a distributed control policy to achieve rendezvous by a set of robots even when some robots in the system do not follow the prescribed policy. These nonconforming robots correspond to faults in the multirobot system, and our control policy is thus a fault-tolerant policy. Each robot has a limited sensing range and is able to directly estimate the state of only those robots within that sensing range, which induces a network topology for the multirobot system. We assume that it is not possible for the fault-free robots to identify the faulty robots, and thus our approach is robust even to undetected faults in the system. The main contribution of this paper is a fault-tolerant distributed control algorithm that is guaranteed to converge to consensus under certain reasonable connectivity conditions. We first present a general algorithm that exploits the notion of a Tverberg partition of a point set in Rd, and give a proof of convergence. We then provide three instantiations of this algorithm, based on three different sensing models. For each case, we analyze performance via extensive simulations. The effectiveness and performance of our algorithms on real platforms are demonstrated through experiments on a multirobot testbed.

In this paper, we explore the problem of rendezvous of synchronous multi-robot systems. Each robot has its own unique, bounded yet controllable sensing range which can be adjusted. The state of those robots within the sensing range can be estimated, which induces the directed network topology of the multi-robot systems. In particular, we consider multi-robot systems containing faulty robots which can behave arbitrarily. Our recent work [1] has addressed the problem of achieving rendezvous in the presence of faulty robots under a restrictive class of conditions on network topology. In this work, we presented a theoretically correct, but computationally intractable algorithm. We extend our past work by proposing a new approximate algorithm that is computationally efficient, and by showing that the proposed algorithm solves our problem given faulty robots in general configurations under mild assumptions on the network topology. Thus, the main contribution of this paper is to provide an efficient computational framework and analysis of robust rendezvous algorithm in the presence of faulty robots. Several simulation results are provided to demonstrate that our algorithm performs well in the face of both stationary and dynamic faults.

It is challenging to analyze the aerial locomotion of bats because of the complicated and intricate relationship between their morphology and flight capabilities. Developing a biologically inspired bat robot would yield insight into how bats control their body attitude and position through the complex interaction of nonlinear forces (e.g., aerodynamic) and their intricate musculoskeletal mechanism. The current work introduces a biologically inspired soft robot called Bat Bot (B2). The overall system is a flapping machine with 5 Degrees of Actuation (DoA). This work reports on some of the preliminary untethered flights of B2. B2 has a nontrivial morphology and it has been designed after examining several biological bats. Key DoAs, which contribute significantly to bat flight, are picked and incorporated in B2's flight mechanism design. These DoAs are: 1) forelimb flapping motion, 2) forelimb mediolateral motion (folding and unfolding) and 3) hindlimb dorsoventral motion (upward and downward movement).

In this paper, we address the problem of planning optimal zero moment point (ZMP) trajectories for the double support phase in bipedal gaits that alternate between single and double support. This is achieved by allowing pre- and post-actuation during the single support phases. Thus, we solve two coupled problems: exact tracking of a given desired ZMP trajectory in the pre- and post-phases (single support), and determination of the desired ZMP during the transition phase (double support). Both are solved while minimizing the overall control energy. We also provide a formal method to assess how the choice of desired ZMP trajectory during the single support phases impacts the overall energy expended during the footstep cycle. Although the obtained solution may not be physically feasible in general, it represents a benchmark to which alternative feasible solutions may be compared. Our approach generalizes previous results that consider only constant output in the pre- and post-phases e.g., allowing pre- and post-phase output from a family of polynomial splines. We evaluate the approach via simulations.

We present a simultaneous localization and mapping (SLAM) algorithm that uses Bézier curves as static landmark primitives rather than sparse feature points. Our approach allows us to estimate the full 6-DOF pose of a robot while providing a structured map which can be used to assist a robot in motion planning and control. We demonstrate how to reconstruct the 3-D location of curve landmarks from a stereo pair without searching for point-based stereo correspondences and how to compare the 3-D shape of curve landmarks between chronologically sequential stereo frames to solve the data association problem. We present a method to combine curve landmarks for mapping purposes, resulting in a map with a continuous set of curves that contain fewer landmark states than conventional sparse point-based SLAM algorithms. Note, to combine curves, we assume the curved landmarks are fixed to a larger curved object naturally occurring in the scene. While our algorithm is less accurate than point-based SLAM algorithms, we are able to create maps with considerably less landmark states and our algorithm can operate in settings lacking texture.

In this paper, we present an omnidirectional-vision-based localization and mapping system which can detect whether a robotic mower is contained in a permitted area. We exploit a robot-centric mapping framework that exploits a differential equation of motion of the landmarks, which are referenced with respect to the robot body frame. The estimator in our system generates a 3D point-based map with landmarks. Concurrently, the estimator defines a boundary of the mowing area with the estimated trajectory of the mower. The estimated boundary and the landmark map are provided for the estimation of the mowing location and for the containment detection. We validate the effectiveness of our system through numerical simulations and present the results of the outdoor experiment that we conducted with our robotic mower.

In this paper, we address the problem of gait generation for bipedal robots. We cast the determination of a Center of Mass (CoM) reference trajectory for a given Zero Moment Point (ZMP) desired behaviour as a stable inversion problem for non-minimum phase systems and obtain an analytical solution for any given ZMP trajectory. Our method exploits results from our previous research, in which we derived a family of bounded CoM trajectories associated to a given desired ZMP trajectory.

In this paper, we propose a distributed control policy to achieve rendezvous by a set of robots even when some robots in the system do not follow the prescribed policy. These nonconforming robots correspond to faults in the multi-robot systems, and our control policy is thus a fault-tolerant policy. We consider the case in which each robot is an autonomous decision maker that is anonymous (i.e., robots are indistinguishable to one another), memoryless (i.e., each robot makes decisions based upon only its current information), and dimensionless (i.e., collision checking is not considered). Each robot has a limited sensing range, and is able to directly estimate the state of only those robots within that sensing range, which induces a network topology for the multi-robot systems. We assume that it is not possible for the fault-free robots to identify the faulty robots (e.g., due to the anonymous property of the robots). Our main result is a practical algorithm that achieves approximate rendezvous in the face of faulty robots under a few assumptions on the network topology. In simulation results, we show that our algorithm performs better in the face of faulty robots than other contemporary convergence algorithms, e.g., the circumcenter law, and local coordinate averaging.

This paper presents a systematic flight controller design based on the mathematics of parametrized manifolds and calculus of variations for the Bat Bot (B2), which possesses many articulated wings. Wing kinematics and morphological properties are crucial in the powered flight of flying vertebrates. The articulated skeleton of these mammals, which contains many degrees of actuation and underactuation, has made it difficult to understand the connection between the bat's flight dynamics and its intricate array of physiological and morphological specializations. B2 is a biomimetic micro aerial vehicle (MAV) that possesses similar morphological properties to a bat in order to duplicate bats powered ballistic motion. In an effort to design the advanced flight control algorithm for B2, this paper reports two major contributions. First, a systematic mathematical framework is introduced that evaluates the holonomically-constrained Lagrangian model of a flapping robot with specified active and passive degrees of freedom (DoF) in order to locate physically feasible and biologically meaningful periodic solutions using optimization. These are parametrized constraint manifolds; the flapping wing dynamics are governed by these manifolds. Second, calculus of variations and the well-recognized method of inverse dynamics are applied in order to synthesize the flight control algorithm for the flapping wings.

This paper presents a distributed robust deployment algorithm for optimal coverage by a mobile sensor network (MSN). Much past research has focused on versions of the coverage problem that partition the workspace into regions, and then assign exactly one sensor to cover each region. For this case it has been shown that the optimal partition is the Voronoi partition, and that Lloyd's algorithm converges to the optimal solution, with each sensor located at the centroid of its Voronoi region. In this paper, we consider the case in which k sensors are assigned to each region in the partition, in order to obtain coverage that is robust to sensor failure. For this case, we prove that the optimal workspace partition is the order-k Voronoi partition, with each sensor assigned to those order-k Voronoi regions for which it is a generator. The collection of these regions for a given sensor defines its effective sensing region (ESR), and we prove that in the optimal configuration each sensor is located at the centroid of its ESR. Finally we introduce a distributed algorithm for our optimal sensor placement problem that requires only simple peer-to-peer (P2P) communications. We show via simulation results that our algorithm converges in finite time, and provides competitive coverage performance in the presence of individual node failures.

This paper presents an approach for modeling user's driving-characteristics in a steering task, and determining the parameters of a virtual fixture to assist the user-control on the basis of his/her task-performances. First, we briefly introduce our assistive human-robot interaction (HRI) interface and a virtual fixture as backgrounds related to this research. The designed HRI interface provides assistance by actively constraining the user-control with a virtual fixture. Second, we discuss a way to model a user's driving-characteristics in a steering task. In modeling the driving-characteristics, we use techniques from inverse optimal control (IOC), where known basis functions (speed, steering, and proximities to inner/outer road boundary) are employed to design a cost function. Third, we describe the experimental setup and procedures to obtain user-demonstrated data from human subjects. Utilizing the obtained data sets, we infer the unknown parameter vector by solving inverse optimal control. Afterward, the user's driving-characteristics are expressed in terms of the balances of the inferred parameters, allowing us to find a relationship between the modeled driving-characteristics and task-completion time. Finally, we present a method to set a virtual fixture for a newly given task by predicting the user's task-performances.

In this paper, we consider the problem of designing distributed control algorithms to solve the rendezvous problem for multi-robot systems with limited sensing, for situation in which random nodes may fail during execution. We first formulate a distributed solution based upon averaging algorithms that have been reported in the consensus literature. In this case, at each stage of execution a 1-step sequential optimal control (i.e., naïve greedy algorithm) is used. We show that by choosing an appropriate constraint set, finite-time point convergence is guaranteed. We then propose a distributed stochastic optimal control algorithm that minimizes a mean-variance cost function for each stage, given that the probability distribution for possible node failures is known a priori. We show via simulation results that our algorithm provides competitive rendezvous task performance in comparison to that of the classical circumcenter algorithm for cases in which there are no node failures. Then we show, via examples with multiple node failures, that our proposed algorithm provides better rendezvous task performance than contemporary algorithms in cases for which failures occur. Additionally, we generate and compare a spectrum of results by varying the probabilities of node failures, or varying the weight value for the variance term in the cost functional. The results suggest that by choosing the design parameters appropriately, one may adjust the degree of soft constraints of the controller as well.

In this paper, we suggest a new way to plan coverage paths for a mobile robot whose position and velocity are subject to bounded error. Most prior approaches assume a probabilistic model of uncertainty and maximize the expected value of covered area. We assume a worst-case model of uncertainty and-for a particular choice of coverage path-are still able to guarantee complete coverage. We begin by considering the special case in which the region to be covered is a single point. The machinery we develop to express and solve this problem immediately extends to guarantee coverage of a small subset in the workspace. Finally, we use this subset as a sort of virtual coverage implement, achieving complete coverage of the entire workspace by tiling copies of the subset along boustrophedon paths.

In this paper, we consider the problem of worst-case performance by a mobile sensor network (MSN) when some of the nodes in the network fail. We formulate the problem as a game in which some subset of the nodes act in an adversarial manner, choosing their motion strategies to maximally degrade overall performance of the network as a whole. We restrict our attention in the present paper to a target detection problem in which the goal is to minimize the probability of missed detection. We use a partitioned cost function that is minimized when each sensor executes a motion strategy given by Lloyd's algorithm (i.e., each agent moves toward the centroid of its Voronoi partition at each time instant), and when the probability of missed detection for each functioning sensor increases with the distance between sensor and target for correctly functioning sensors; adversarial nodes in the network are unable to detect the target, and move to maximally increase the probability of missed detection by the properly functioning sensors. We pose the problem as a multi-stage decision process, and use forward dynamic programming over a finite horizon to numerically compute optimal strategies for the adversaries. We compare the resulting strategies to a greedy algorithm, providing both system trajectories and evolution of the probability of missed detection during execution.

In this paper, we address the problem of egomotion estimation using an inertial measurement unit and visual observations of planar features on the ground. The main practical difficulty of such a system is correctly determining the ground planar features from the visual observations. Herein, we propose a novel vision-aided inertial navigation system through simultaneous motion estimation and ground plane feature detection. We present a state-space formulation for the pose estimation problem and solve it via an augmented unscented Kalman filter. First, the predictions obtained by the Kalman filter are used to detect the ground plane features. Second, the detected features are fed back to the motion estimation algorithm to be used in the measurement update phase of the filter. The developed detection algorithm consists of two steps, namely homography-based and normal-based outlier rejection. The presented integration algorithm allows 6-DoF motion estimation in a practical scenario where the camera is not restricted to observe only the ground plane. Real-world experiments in an indoor scenario indicate the accuracy and reliability of our proposed method in the presence of outliers and non-ground obstacles.

This paper presents a novel vision-based localization and mapping algorithm using image moments of region features. The environment is represented using regions, such as planes and/or 3D objects instead of only a dense set of feature points. The regions can be uniquely defined using a small number of parameters; e.g., a plane can be completely characterized by normal vector and distance to a local coordinate frame attached to the plane. The variation of image moments of the regions in successive images can be related to the parameters of the regions. Instead of tracking a large number of feature points, variations of image moments of regions can be computed by tracking the segmented regions or a few feature points on the objects in successive images. A map represented by regions can be characterized using a minimal set of parameters. The problem is formulated as a nonlinear filtering problem. A new discrete-time nonlinear filter based on the state-dependent coefficient (SDC) form of nonlinear functions is presented. It is shown via Monte-Carlo simulations that the new nonlinear filter is more accurate and consistent than EKF by evaluating the root-mean squared error (RMSE) and normalized estimation error squared (NEES).

This paper addresses the problem of motion planning for fast, agile flight through a dense obstacle field. A key contribution is the design of two families of motion primitives for aerial robots flying in dense obstacle fields, along with rules to stitch them together. The primitives are obtained by solving for the flight dynamics of the aerial robot, and explicitly account for limited agility using time delays. The first family of primitives consists of turning maneuvers to link any two points in space. The locations of the terminal points are used to obtain closed-form expressions for the control inputs required to fly between them, while accounting for the finite time required to switch between consecutive sets of control inputs. The second family consists of aggressive turn-around maneuvers wherein the time delay between the angle of attack and roll angle commands is used to optimize the maneuver for the spatial constraints. A 3-D motion planning algorithm based on these primitives is presented for aircraft flying through a dense forest.

In this paper, we consider the performance of distributed control algorithms for networked robotic systems when one or more robots fail to execute the optimal policy. In particular, we investigate the performance of the circumcenter algorithm with connectivity maintenance [1]-[3] when one or more adversarial agents act maliciously to maximally disrupt convergence of the remaining, cooperative agents. To this end, we formulate a performance objective for each adversary node in terms of the circumradii of its cooperative neighbors in a communication graph which does not require omniscience of adversaries as is often assumed in the literature (e.g., [4], [5]). We provide an optimization algorithm based on finite-horizon dynamic programming, and obtain solutions through numerical simulation. Our results show that in general adversarial nodes are able not only to impede convergence toward consensus, but can also affect global changes in the topology of the communication graph for the cooperative agents.

This paper presents a vision-based localization and mapping algorithm for an autonomous mower. We divide the task for robotic mowing into two separate phases, a teaching phase and a mowing phase. During the teaching phase, the mower estimates the 3D positions of landmarks and defines a boundary in the lawn with an estimate of its own trajectory. During the mowing phase, the location of the mower is estimated using the landmark and boundary map acquired from the teaching phase. Of particular interest for our work is ensuring that the estimator for landmark mapping will not fail due to the nonlinearity of the system during the teaching phase. A nonlinear observer is designed with pseudo-measurements of each landmark's depth to prevent the map estimator from diverging. Simultaneously, the boundary is estimated with an EKF. Measurements taken from an omnidirectional camera, an IMU, and a ground speed sensor are used for the estimation. Numerical simulations and offline teaching phase experiments with our autonomous mower demonstrate the potential of our algorithm.

In this paper, we consider the problem of an autonomous robot searching for a target object whose position is characterized by a prior probability distribution over the workspace (the object prior). We consider the case of a continuous search domain, and a robot equipped with a single binary sensor whose ability to recognize the target object varies probabilistically as a function of the distance from the robot to the target (the sensor model). We show that when the object prior and sensor model are taken from the exponential family of distributions, the searcher's posterior probability map for the object location belongs to a finitely parameterizable class of functions, admitting an exact representation of the searcher's evolving belief. Unfortunately, the cost of the representation grows exponentially with the number of stages in the search. For this reason, we develop an approximation scheme that exploits regularized particle filtering methods. We present simulation studies for several scenarios to demonstrate the effectiveness of our approach using a simple, greedy search strategy.

A common algorithm for deployment of a mobile sensor network in a bounded domain moves each sensor toward the centroid of its Voronoi cell. This algorithm is optimal for a particular cost function that is expressed as a sum over Voronoi cells, where the placement of a sensor in its own cell has no effect on cost in other cells. We provide a probabilistic interpretation of this “partitioned” cost function in the context of a target detection task, where each sensor has a chance of seeing the target that decreases monotonically with distance and where the goal is to minimize the total probability of missed detection. We show that the partitioned cost function is exactly the probability of missed detection given that a sensor can only see a target in its own Voronoi cell. We derive the probability of missed detection in the general case - where each sensor might see the target anywhere - and show that optimal sensor placement changes. Finally, we derive the probability of missed detection given the possibility of sensor failure, producing a robust measure of cost with respect to which optimal sensor placement is different yet again. Our results are illustrated by several examples in simulation.

In this paper, we address the problem determining the connectivity of a robot's free configuration space. Our method iteratively builds a constructive proof that two configurations lie in disjoint components of the free configuration space. Our algorithm first generates samples that correspond to configurations for which the robot is in collision with an obstacle. These samples are then weighted by their generalized penetration distance, and used to construct alpha shapes. The alpha shape defines a collection of simplices that are fully contained within the configuration space obstacle region. These simplices can be used to quickly solve connectivity queries, which in turn can be used to define termination conditions for sampling-based planners. Such planners, while typically either resolution complete or probabilistically complete, are not able to determine when a path does not exist, and therefore would otherwise rely on heuristics to determine when the search for a free path should be abandoned. An implementation of the algorithm is provided for the case of a 3D Euclidean configuration space, and a proof of correctness is provided.

Existing approaches to visual Simultaneous Localization and Mapping (SLAM) typically utilize points as visual feature primitives to represent landmarks in the environment. Since these techniques mostly use image points from a standard feature point detector, they do not explicitly map objects or regions of interest. Our work is motivated by the need for different SLAM techniques in path and riverine settings, where feature points can be scarce or may not adequately represent the environment. Accordingly, the proposed approach uses cubic Bézier curves as stereo vision primitives and offers a novel SLAM formulation to update the curve parameters and vehicle pose. This method eliminates the need for point-based stereo matching, with an optimization procedure to directly extract the curve information in the world frame from noisy edge measurements. Further, the proposed algorithm enables navigation with fewer feature states than most point-based techniques, and is able to produce a map which only provides detail in key areas. Results in simulation and with vision data validate that the proposed method can be effective in estimating the 6DOF pose of the stereo camera, and can produce structured, uncluttered maps.

A ubiquitous problem in robotics is determining policies that move robots with uncertain process and observation models (partially-observed state systems) to a goal configuration while avoiding collision. We propose a new method to solve this minimum uncertainty navigation problem. We use a continuous partially-observable Markov decision process (POMDP) model and optimize an objective function that considers both probability of collision and uncertainty at the goal position. By using information-theoretic heuristics, we are able to find policies that are effective for both minimizing collisions and stopping near the goal configuration. We additionally introduce a filtering algorithm that tracks collision free trajectories and estimates the probability of collision.

This paper presents an optimal feedback control scheme to drive a vehicle equipped with a limited Field-Of-View (FOV) camera towards a desired position following the shortest path and keeping a given landmark in sight. Based on the shortest path synthesis available from previous works, feedback control laws are defined for any point on the motion plane exploiting geometric properties of the synthesis itself. Moreover, by using a slightly generalized stability analysis setting, which is that of stability on a manifold, a proof of stability is given. Reported simulations demonstrate the effectiveness of the proposed technique.

In this paper, we propose a novel system architecture and control scheme, a human-machine perceptual feedback system and control, to enhance a user's control performance while he is teleoperating a mobile robot with a joystick. First, we model the user, robot, and human-machine perceptual feedback controller. The two key roles of the controller are: a) displaying a preferred road width to the user with respect to various road types, and b) constraining the maximum linear and angular velocity of the robot for safer maneuver as well. Second, we define a perception to behavior stability and perform a stability analysis. Finally, we present simulation results showing that a novice user can teleoperate the mobile robot successfully along sidewalks by our approach.

We propose a planning algorithm that allows user-supplied domain knowledge to be exploited in the synthesis of information feedback policies for systems modeled as partially observable Markov decision processes (POMDPs). POMDP models, which are increasingly popular in the robotics literature, permit a planner to consider future uncertainty in both the application of actions and sensing of observations. With our approach, domain experts can inject specialized knowledge into the planning process by providing a set of local policies that are used as primitives by the planner. If the local policies are chosen appropriately, the planner can evaluate further into the future, even for large problems, which can lead to better overall policies at decreased computational cost. We use a structured approach to encode the provided domain knowledge into the value function approximation. We demonstrate our approach on a multi-robot fire fighting problem, in which a team of robots cooperates to extinguish a spreading fire, modeled as a stochastic process. The state space for this problem is significantly larger than is typical in the POMDP literature, and the geometry of the problem allows for the application of an intuitive set of local policies, thus demonstrating the effectiveness of our approach.

We propose a new minimum uncertainty planning technique for mobile robots localizing with beacons. We model the system as a partially-observable Markov decision process and use a sampling-based method in the belief space (the space of posterior probability density functions over the state space) to find a belief-feedback policy. This approach allows us to analyze the evolution of the belief more accurately, which can result in improved policies when common approximations do not model the true behavior of the system. We demonstrate that our method performs comparatively, and in certain cases better, than current methods in the literature.

In this paper, we present a visual servo controller that effects optimal paths for a nonholonomic differential drive robot with field-of-view constraints imposed by the vision system. The control scheme relies on the computation of homographies between current and goal images, but unlike previous homography-based methods, it does not use the homography to compute estimates of pose parameters. Instead, the control laws are directly expressed in terms of individual entries in the homography matrix. In particular, we develop individual control laws for the three path classes that define the language of optimal paths: rotations, straight-line segments, and logarithmic spirals. These control laws, as well as the switching conditions that define how to sequence path segments, are defined in terms of the entries of homography matrices. The selection of the corresponding control law requires the homography decomposition before starting the navigation. We provide a controllability and stability analysis for our system and give experimental results.

A catadioptric vision system combines a camera and a mirror to achieve a wide field of view imaging system. This type of vision system has many potential applications in mobile robotics. This paper is concerned with the design of a robust image-based control scheme using a catadioptric vision system mounted on a mobile robot. We exploit the fact that the decoupling property contributes to the robustness of a control method. More precisely, from the image of a point, we propose a minimal and decoupled set of features measurable on any catadioptric vision system. Using the minimal set, a classical control method is proved to be robust in the presence of point range errors. Finally, experimental results with a coarsely calibrated mobile robot validate the robustness of the new decoupled scheme.

Information-feedback control schemes (more specifically, sensor-based control schemes) select an action at each stage based on the sensory data provided at that stage. Since it is impossible to know future sensor readings in advance, predicting the future behavior of a system becomes difficult. Hyper-particle filtering is a sequential computational scheme that enables probabilistic evaluation of future system performance in the face of this uncertainty. Rather than evaluating individual sample paths or relying on point estimates of state, hyper-particle filtering maintains at each stage an approximation of the full probability density function over the belief space (i.e., the space of possible posterior densities for the state estimate). By applying hyper-particle filtering, control policies can be more more accurately assessed and can be evaluated from one stage to the next. These aspects of hyper-particle filtering may prove to be useful when determining policies, not just when evaluating them.

In this paper, we formalize the problem of partial barrier coverage, that is, the problem of using robot sensors (guards) to minimize the probability of undetected intrusion in a particular region by an intruder. We use ideas from noncooperative game theory together with previous results from complete barrier coverage - the problem of completely preventing undetected intrusion - to develop new methods that solve this problem for the specific case of bounded-range line-of-sight sensors in a two-dimensional polygonally-bounded region. Our solution constructs equilibrium strategies for the intruder and guards, and calculates the level of partial coverage.

In this paper we consider the problem of maintaining visibility of a moving evader by a mobile robot, the pursuer, in an environment with obstacles. We simultaneously consider bounded speed for both players and a variable distance separating them. Unlike our previous efforts [R. Murrieta-Cid et al., 2007], we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations. We approach evader tracking by decomposing the environment into convex regions. We define two graphs: one is called the mutual visibility graph (MVG) and the other the accessibility graph (AG). The MVG provides a sufficient condition to maintain visibility of the evader while the AG defines possible regions to which either the pursuer or the evader may go to. The problem is framed as a non cooperative game. We establish the existence of a solution, based on a k- Min approach, for the following givens: the environment, the initial state of the evader and the pursuer, including their maximal speeds. We show that the problem of finding a solution to this game is NP-complete.

Control of wheeled vehicles is a difficult problem due to nonholonomic constraints. This problem is compounded by sensor limitations. A previously developed control scheme for a wheeled robot, which keeps a target in the view of a mounted camera, is one solution to the problem. In this paper, we prove the controllability and stability of the control scheme. We present an implementation of the controller, as well as present the results of simulations and physical experiments.

In this paper, we formalize the problem of barrier coverage, that is, the problem of preventing undetected intrusion in a particular region using robot sensors. We solve the problem of finding the minimum-length barrier in the case of variable bounded-range line-of-sight sensors in a two-dimensional polygonally-bounded region. We do this by building a graph of candidate barriers that could potentially be in the minimum barrier. The dual of this graph shows the connectivity of the free space. We thus reduce the problem to the network flows maximum-flow/minimum-cut problem.

This paper presents a switched homography-based visual control for differential drive vehicles. The goal is defined by an image taken at the desired position, which is the only previous information needed from the scene. The control takes into account the field-of-view constraints of the vision system through the specific design of the paths with optimality criteria. The optimal paths consist of straight lines and curves that saturate the sensor viewing angle. We present the controls that move the robot along these paths based on the convergence of the elements of the homography matrix. Our contribution is the design of the switched homography-based control, following optimal paths guaranteeing the visibility of the target.

In this paper, we consider the problem of planning optimal paths for a differential-drive robot with limited sensing, that must maintain visibility of a fixed landmark as it navigates in its environment. In particular, we assume that the robot's vision sensor has a limited field of view (FOV), and that the fixed landmark must remain within the FOV throughout the robot's motion. We first investigate the nature of extremal paths that satisfy the FOV constraint. These extremal paths saturate the camera pan angle. We then show that optimal paths are composed of straight-line segments and sections of these these extremal paths. We provide the complete characterization of the shortest paths for the system by partitioning the plane into a set of disjoint regions, such that the structure of the optimal path is invariant over the individual regions

Visual servoing methods are commonly classified as image-based or position-based, depending on whether image features or the camera position define the signal error in the feedback loop of the control law. Choosing one method over the other gives asymptotic stability of the chosen error but surrenders control over the other. This can lead to system failure if feature points are lost or the robot moves to the end of its reachable space. We present a hybrid switched-system visual servo method that utilizes both image-based and position-based control laws. We prove the stability of a specific, state-based switching scheme and present simulated and experimental results.

This work presents the proof of controllability for a differential drive robot that maintains visibility of a landmark. The robot has limited sensing capabilities (angle of view). We also present properties of optimal paths for this system

This paper presents a passage potential based biasing scheme for PRMs to specifically address the narrow passage problem. The biasing strategy fulfills minimum requirements for an efficient biasing, considering not only location issues, but also intensity, sparseness and applicability of the biasing criterion. Conforming to these features a particular family of passage potential functions has been defined and integrated within a basic PRM to achieve biasing. Simulations have demonstrated the reliable and successful implementation of the proposed architecture under several experimental settings and robot configurations

Vision-based control of wheeled vehicles is a difficult problem due to nonholonomic constraints on velocities. This is further complicated in the control of vehicles with drift terms and dynamics containing fewer actuators than velocity terms. We explore one such system, the wheeled inverted pendulum, embodied by the Segway. We present two methods of eliminating the effects of nonactuated attitude motions and a novel controller based on partial feedback linearization. This novel controller outperforms a controller based on typical linearization about an equilibrium point

In many multirobot applications, the specific assignment of goal configurations to robots is less important than the overall behavior of the robot formation. In such cases, it is convenient to define a permutation-invariant multirobot formation as a set of robot configurations, without assigning specific configurations to specific robots. For the case of robots that translate in the plane, we can represent such a formation by the coefficients of a complex polynomial whose roots represent the robot configurations. Since these coefficients are invariant with respect to permutation of the roots of the polynomial, they provide an effective representation for permutation-invariant formations. In this paper, we extend this idea to build a full representation of a permutation-invariant formation space. We describe the properties of the representation, and show how it can be used to construct collision-free paths for permutation-invariant formations

In this paper we demonstrate path planning for our formation space that represents permutation-invariant multi-robot formations. Earlier methods generally pre-assign roles for each individual robot, rely on local planning and behaviors to build emergent behaviors, or give robots implicit constraints to meet. Our method first directly plans the formation as a set, and only afterwards determines which robot takes which role. To build our representation of this formation space, we make use of a property of complex polynomials: they are unchanged by permutations of their roots. Thus we build a characteristic polynomial whose roots are the robot locations, and use its coefficients as a representation of the formation. Mappings between work spaces and formation spaces amount to building and solving polynomials. In this paper, we construct an efficient obstacle collision detector, and use it in a local planner. From this we construct a basic roadmap planner. We thus demonstrate that our polynomial based representation can be used for effective permutation invariant formation planning.

In this paper, we consider the surveillance problem of maintaining visibility at a fixed distance of a mobile evader using a mobile robot equipped with sensors. Optimal motion for the target to escape is found. Symmetrically, an optimal motion strategy for the observer to always maintain visibility of the evader is determined. The optimal motion strategies proposed in this paper are based on critical events. The critical events are defined with respect to the obstacles in the environment.

In this paper we address the problem of generating a motion strategy to find an object in a known 3-D environment as quickly as possible on average. We use a sampling scheme that generates an initial set of sensing locations for the robot and then we propose a convex cover algorithm based on this sampling. Our algorithm tries to reduce the cardinality of the resulting set and has the main advantage of scaling well with the dimensionality of the environment. We then use the resulting convex covering to generate a graph that captures the connectivity of the workspace. Finally, we search this graph to generate trajectories that try to minimize the expected value of the time to find the object.

In this paper we consider the problem of maintaining surveillance of a moving the target by a nonholonomic mobile observer. The observer's goal is to maintain visibility of the target from a predefined, fixed distance, l. The target escapes if (a) it moves behind an obstacle to occlude the observer's view, (b) it causes the observer to collide with an obstacle, or (c) it exploits the nonholonomic constraints on the observer motion to increase its distance from the observer beyond the surveillance distance l. We deal specifically with the situation in which the only constraint on the target's velocity is a bound on speed (i.e., there are no nonholonomic constraints on the target's motion), and the observer is a nonholonomic, differential drive system having bounded speed. We develop the system model, from which we derive a lower bound for the required observer speed. Finally, we consider the effect of obstacles on the observer's ability to successfully track the target.

In this paper we describe a new representation for a configuration space for formations of robots that translate in the plane. What makes this representation unique is that it is permutation-invariant, so the relabeling of robots does not affect the configuration. Earlier methods generally either pre-assign roles for each individual robot, or rely on local planning and behaviors to build emergent behaviors. Our method first plans the formation as a set, and only afterwards determines which robot takes which role. To build our representation of this formation space, we make use of a property of complex polynomials: they are unchanged by permutations of their roots. Thus we build a characteristic polynomial whose roots are the robot locations, and use its coefficients as a representation. Mappings between work spaces and formation spaces amount to building and solving polynomials. In this paper we also perform basic path planning on this new representation, and show some practical and theoretical properties. We show that the paths generated are invariant-relative to their endpoints - with respect to linear coordinate transforms, and in most cases produce reasonable, if not linear, paths from start to finish.

This work addresses the problem of computing the motions of a robot observer in order to maintain visibility of a moving target at a fixed surveillance distance. In this paper, we deal specifically with the situation in which the observer has bounded velocity. We give necessary conditions for the existence of a surveillance strategy and give an algorithm that generates surveillance strategies.

This work presents the minimal length paths, for a robot that maintains visibility of a landmark. The robot is a differential drive system and has limited sensing capabilities (range and angle of view). The optimal paths are composed of straight lines and curves that saturate the camera pan angle.

Image matching via multiresolution critical-point hierarchies has been shown to be useful in feature point selection, real-time tracking, volume rendering, and image interpolation. Drawbacks of the method include computational complexity and a lack of constraints on rigid motion. In this paper we present a method by which robot end-effector velocities are tracked using the condensation algorithm and critical-point image observations. By using a window-based approach, we immediately reduce complexity while imposing constraints on camera motion. We show that the critical-point observations are successful in estimating camera motion by evaluating the similarity of sample windows.

We present an example of the use of multi-attribute utility analysis in the design of a robot system. Multi-attribute utility analysis is a tool used by systems engineers to aid in deciding amongst numerous alternatives. Its strength lies in the fact that very different metrics can be compared, and that it takes unto account human preferences and risk attitudes. As a design tool, multi-attribute utility analysis is performed off line, during the system design phase, to choose among possible designs, components, gains, etc. We offer a demonstration of multi-attribute utility analysis in designing a hybrid switched-system visual servo system. We have previously introduced such a system, and here use multi-attribute utility analysis to select a switching algorithm that best suits the needs of a specific user.

In this paper we address the problem of finding time optimal search paths in known environments. In particular, the task is to search a known environment for an object whose unknown location is characterized by a known probability density function (pdf). With this formulation, the time required to find the object is a random variable induced by the choice of search path together with the pdf for the object's location. The optimization problem is to find the path that yields the minimum expected value of the time required to find the object. We propose a two layered approach. Our algorithm first determines an efficient ordering of visiting regions in a decomposition that is defined by critical curves that are related to the aspect graph of the space to be searched. It then generates locally optimal trajectories within each of these regions to construct a complete continuous path. We have implemented this algorithm and present results.

In this paper, we propose a new method for object tracking, which is primarily based on the results from prof. Shinagawa's image matching. We provide a method that tracks an object and follows it in real-time through a sequence of images which are given, for example, by a robotic camera. The main feature of the method is that it is not affected by the movements (within a certain reasonable range) of the camera or the object; such as, translation, rotation or scaling. The algorithm is also insensible to regular changes of the object's shape. For real-time applications, the algorithm allows the tracking of an object through a sequence of 64*64 images, at a rate of over 8 frames/second.

In the recent past, many researchers have developed control algorithms for visual servo applications. In this paper, we introduce a new hybrid switched system approach, in which a high-level decision maker selects between two visual servo controllers. We have evaluated our approach with simulations and experiments using three individual visual servo systems and three candidate switching rules. The proposed method is very promising for visual servo tasks in which there is a significant distance between the initial and goal configuration, or the task is one that can cause an individual visual servo system to fail.

In this paper we examine the selection of feature points for visual servoing methods using multiresolution critical-point filters (CPF). With the increased number of feature points made available to us using CPF, we hope to improve the robustness of the system by allowing the algorithm to automatically detect usable feature points on virtually any object without any a priori knowledge of the object. Furthermore, the algorithm revises these points at each iteration to account for events that may have otherwise caused feature points to be lost and led to the visual servo method ending in failure.

In this paper we consider the problem of automatically determining whether regions in an outdoor environment can be traversed by a mobile robot. We propose a two-level classifier that uses data from a single color image to make this determination. At the low level, we have implemented three classifiers based on color histograms, directional filters and local binary patterns. The outputs of these low level classifiers are combined using a voting scheme that weights the results of each classifier using an estimate of its error probability. We present results from a large number of trials using a database of representative images acquired in real outdoor environments.

Visual servoing methods are commonly classified as image based or position based, depending on whether image features or the robot pose is used in the feedback loop of the control law. Choosing one method over the other gives stability in the chosen state but surrenders all control over the other, which can lead to system failure if feature points are lost or the robot moves to the end of its reachable space. We present a hybrid switched system visual servo method that utilizes both image based and position based control laws. Through a switching scheme we present, this method provides asymptotic stability in both the image and pose and prevent system failure.

This paper deals with the problem of computing the motions of a robot observer in order to maintain visibility of a moving target. The target moves unpredictably, and the distribution of obstacles in the workspace is known in advance. Our algorithm computes a motion strategy based on partitioning the configuration space and the workspace in non-critical regions separated by critical curves. In this work, the existence of a solution for a given polygon and delay are determined.

In this paper, we propose an approach to solve the problem of finding an object in a polygon which may contain holes. We define an optimal solution as the route that minimizes the expected time it takes to find said object. The object search problem is shown to be NP-hard by reduction, therefore, we propose the heuristic of an utility function, defined as the ratio of a gain over a cost and a greedy algorithm in a reduced search space that is able to explore several steps ahead without incurring in too high computational cost. This approach was implemented and simulation results are shown.

Probabilistic roadmaps (PRMs) are a popular representation used by many current path planners. Construction of a PRM requires the ability to generate a set of random samples from the robot's configuration space, and much recent research has concentrated on new methods to do this. In this paper, we present a sampling scheme that is based on the manipulability measure associated with a robot arm. Intuitively, manipulability characterizes the arm's freedom of motion for a given configuration. Thus, our approach is to densely sample those regions of the configuration space in which manipulability is low (and therefore, the robot has less dexterity), while sampling more sparsely those regions in which the manipulability is high. We have implemented our approach, and performed extensive evaluations using prototypical problems from the path planning literature. Our results show this new sampling scheme to be effective in generating PRMs that can solve a large range of path planning problems.

Coordinating the motions of multiple robots operating in a shared workspace without collisions is an important capability. We address the task of coordinating the motions of multiple robots when their trajectories (defined by both the path and velocity along the path) are specified. This problem of collision-free trajectory coordination arises in welding and painting workcells in the automotive industry. We identify sufficient and necessary conditions for collision-free coordination of the robots when only the robot start times can be varied, and define corresponding optimization problems. We develop mixed integer programming formulations of these problems to automatically generate minimum time solutions. This method is applicable to both mobile robots and articulated arms, and places no restrictions on the number of degrees of freedom of the robots. The primary advantage of this method is its ability to coordinate the motions of several robots, with as many as 20 robots being considered. We show that, even when the robot trajectories are specified, minimum time coordination of multiple robots is NP-hard.

Visual servoing has been a viable method of robot manipulator control for more than a decade. Image-based visual servoing (IBVS), in particular, has seen considerable development in recent years. Recently, a number of researchers have reported tasks for which traditional IBVS methods fail, or experience serious difficulties. In response to these difficulties, several methods have been devised that partition the control scheme, allowing troublesome motions to be handled by methods that do not rely solely on the image Jacobian. To date, there has been little research that explores the relative strengths and weaknesses of these methods. In this paper we present such an evaluation. We have chosen three recent visual servo approaches for evaluation, in addition to the traditional IBVS approach. We posit a set of performance metrics that measure quantitatively the performance of a visual servo controller for a specific task. We then simulate each of the candidate visual servo methods for four canonical tasks, under perfect and nonideal experimental conditions.

Probabilistic roadmaps (PRMs) are a popular representation used by many current path planners. Construction of a PRM requires the ability to generate a set of random samples from the robot's configuration space, and much recent research has concentrated on new methods to do this. In this paper, we present a sampling scheme that is based on the manipulability measure associated with a robot arm. Intuitively, manipulability characterizes the arm's freedom of motion for a given configuration. Thus, our approach is to sample densely those regions of the configuration space in which manipulability is low (and therefore the robot has less dexterity), while sampling more sparsely those regions in which the manipulability is high. We have implemented our approach, and performed extensive evaluations using prototypical problems from the path planning literature. Our results show this new sampling scheme to be quite effective in generating PRMs that can solve a large range of path planning problems.

We have previously (2000) developed a new method for generating collision-free paths for robots operating in changing environments. Our approach relies on creating a representation of the configuration space that can be easily modified in real time to account for changes in the environment. In this paper we address the issues of efficiency and robustness. First, we develop a novel, efficient encoding scheme that exploits the redundancy in the map from robot's Euclidean workspace to its configuration space. Then, we introduce the concept of /spl epsi/-robustness, and show how it can be used to enhance the representations that are used by the planner. Along the way, we present quantitative results that illustrate the efficiency and robustness of our approach.

We present a new approach to sensor-based navigation in cluttered environments. In our system, tasks are specified in terms of visual goals, and obstacles are detected by a laser range finder. To effect task performance, we introduce a new gain scheduling visual servo controller. Our approach uses a diagonal gain matrix whose entries are adjusted during execution according to one of several proposed gain schedules. Obstacle avoidance is achieved by allowing the detected obstacles to generate artificial repulsive potential fields, which alter the motion of the mobile robot base. Since this motion affects the vision-based control, it is compensated by corresponding camera motions. Finally, we combine the obstacle avoiding and visual servo components of the system so that visual servo tasks can be performed as obstacles are avoided. We illustrate our approach with both simulations and real experiments using our experimental platform H/sup il/are2Bis.

In image-based visual servo control, where control is effected with respect to the image, there is no direct control over the Cartesian velocities of the robot end effector. As a result, the robot executes trajectories that are desirable in the image, but which can be indirect and seemingly contorted in Cartesian space. We introduce a partitioned approach to visual servo control that overcomes this problem. In particular, we decouple the x-axis rotational and translational components of the control from the remaining degrees of freedom. Then, to guarantee that all features remain in the image throughout the entire trajectory, we incorporate a potential function that repels feature points from the boundary of the image plane. We illustrate our control scheme with a variety of results.

In this paper, we present methods for tracking complex, articulated objects. We assume that an appearance model and the kinematic structure of the object to be tracked are given, leading to what is termed a model-based object tracker. At each time step, this tracker observes a new monocular grayscale image of the scene and combines information gathered from this image with knowledge of the previous configuration of the object to estimate the configuration of the object at the time the image was acquired. Each degree of freedom in the model has an uncertainty associated with it, indicating the confidence in the current estimate for that degree of freedom. These uncertainty estimates are updated after each observation. An extended Kalman filter with appropriate observation and system models is used to implement this updating process. The methods that we describe are potentially beneficial to areas such as automated visual tracking in general, visual servo control, and human computer interaction.

Provides a broad sketch of visual servoing, and the application of real-time vision, tracking and control for robot guidance. It outlines the basic theoretical approaches to the problem, describes a typical architecture, and discusses major milestones, applications and the significant vision sub-problems that must be solved.

This paper addresses the visual servoing of robot manipulators in fixed-camera configuration for considering a moving target. We propose a control scheme consisting of two loops: an inner loop which is a joint velocity controller; and an outer loop which is an image-based feedback loop. We present the stability analysis and the experimental evaluation on a two degrees of freedom direct-drive planar robot arm.

The pervasiveness of computers in everyday life coupled with recent rapid advances in computer technology have created both the need and the means for sophisticated human-computer interaction (HCI) technology. Despite all the progress in computer technology and robotic manipulation, the interfaces for controlling manipulators have changed very little in the last decade. Therefore human-computer interfaces for controlling robotic manipulators are of great interest. A flexible and useful robotic manipulator is one capable of movement in three translational degrees of freedom, and three rotational degrees of freedom. In addition to research labs, six degree of freedom robots can be found in construction areas or other environments unfavorable for human beings. This paper proposes an intuitive and convenient visually guided interface for controlling a robot with six degrees of freedom. Two orthogonal cameras are used to track the position and the orientation of the hand of the user. This allows the user to control the robotic arm in a natural way.

This paper proposes an approach for motion planning in indoor environments based on incomplete and uncertain information from a line-based binocular stereo system. The primary goal of the planning process is to plan an optimal path through an unknown or partially known environment, depending on the information gained from exploration and the current mission goal. This paper presents an adaptable motion planner that supports sensor-based map construction, object recognition and navigation in an unknown environment while carrying out a mission. Also presented are some preliminary experimental results that demonstrate the utility of the approach.

Performance estimation for feature tracking is a critical issue, if feature tracking results are to be used intelligently. In this paper, we derive quantitative measures for the spatial accuracy of a particular feature tracker. This method uses the results from the sum-of-squared-differences correlation measure commonly used for feature tracking to estimate the accuracy (in the image plane) of the feature tracking result. In this way, feature tracking results can be analyzed and exploited to a greater extent without placing undue confidence in inaccurate results or throwing out accurate results. We argue that this interpretation of results is more flexible and useful than simply using a confidence measure on tracking results to accept or reject features. For example, and extended Kalman filtering framework can assimilate these tracking results directly to monitor the uncertainty in the estimation process for the state of an articulated object.

We describe a model-based object tracking system that updates the configuration parameters of an object model based upon information gathered from a sequence of monocular images. Realistic object and imaging models are used to determine the expected visibility of object features, and to determine the expected appearance of all visible features. We formulate the tracking problem as one of parameter estimation from partially observed data, and apply the extended Kalman filtering (EKF) algorithm. The models are also used to determine what point feature movement reveals about the configuration parameters of the object. This information is used by the EKF to update estimates for parameters, and for the uncertainty in the current estimates, based on observations of point features in monocular images.

This work makes two contributions to geometric motion planning for multiple robots: 1) motion plans are computed that simultaneously optimize an independent performance measure for each robot; 2) a general spectrum is defined between decoupled and centralized planning, in which we introduce coordination along independent roadmaps. By considering independent performance measures, we introduce a form of optimality that is consistent with concepts from multiobjective optimization and game theory literature. We present implemented, multiple-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: 1) coordination along fixed, independent paths; 2) coordination along independent roadmaps; and 3) general, unconstrained motion planning. Computed examples are presented for all three problem classes that illustrate the concepts and algorithms.

Numerical computation with Bayesian posterior densities has recently received much attention both in the applied statistics and image processing communities. This paper surveys previous literature and presents efficient methods for computing marginal density values for image models that have been widely considered in computer vision and image processing. The particular models chosen are a Markov random field (MRF) formulation, implicit polynomial surface models, and parametric polynomial surface models. The computations can be used to make a variety of statistically based decisions, such as assessing region homogeneity for segmentation or performing model selection. Detailed descriptions of the methods are provided, along with demonstrative experiments on real imagery.

We address the ability of a computer vision system to perceive the motion of an object (possibly a robot manipulator) in its field of view. We derive a quantitative measure of motion perceptibility, which relates the magnitude of the rate of change in an object's position to the magnitude of the rate of change in the image of that object. We then show how motion perceptibility can be combined with the traditional notion of manipulability, into a composite perceptibility/manipulability measure. We demonstrate how this composite measure may be applied to a number of different problems involving relative hand/eye positioning and control.

This work makes two contributions to geometric motion planning for multiple robots: i) motion plans can be determined that simultaneously optimize an independent performance criterion for each robot; ii) a general spectrum is defined between decoupled and centralized planning. By considering independent performance criteria, we introduce a form of optimality that is consistent with concepts from multi-objective optimization and game theory research. Previous multiple-robot motion planning approaches that consider optimality combine individual criteria into a single criterion. As a result, these methods can fail to find many potentially useful motion plans. We present implemented, multi-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: i) coordination along fixed, independent paths; ii) coordination along independent roadmaps; iii) general, unconstrained motion planning. Several computed examples are presented for all three problem classes that illustrate the concepts and algorithms.

Provides a method for characterizing future configurations under the implementation of a motion strategy in the presence of sensing and control uncertainties. We provide general techniques which can apply to either nondeterministic models of uncertainty (as typically considered in preimage planning research) or probabilistic models. Information-space concepts from modern control theory are utilized to define the notion of a strategy in this general context. We have implemented algorithms and show several computed examples that generalize the forward projection concepts from traditional literature in this area.

This article provides a tutorial introduction to visual servo control of robotic manipulators. Since the topic spans many disciplines our goal is limited to providing a basic conceptual framework. We begin by reviewing the prerequisite topics from robotics and computer vision, including a brief review of coordinate transformations, velocity representation, and a description of the geometric aspects of the image formation process. We then present a taxonomy of visual servo control systems. The two major classes of systems, position-based and image-based systems, are then discussed in detail. Since any visual servo system must be capable of tracking image features in a sequence of images, we also include an overview of feature-based and correlation-based methods for tracking. We conclude the tutorial with a number of observations on the current directions of the research field of visual servo control.

Gross-motion planning for assembly is commonly considered as a distinct, isolated step between task sequencing/scheduling and fine-motion planning. In this paper the authors formulate a problem of delivering parts for assembly in a manner that integrates it with both the manufacturing process and the fine motions involved in the final assembly stages. One distinct characteristic of gross-motion planning for assembly is the prevalence of uncertainty involving time-in parts arrival, in request arrival, etc. The authors propose a stochastic representation of the assembly process, and design a state-feedback controller that optimizes the expected time that parts wait to be delivered. This leads to increased performance and a greater likelihood of stability in a manufacturing process. Six specific instances of the general framework are modeled and solved to yield optimal motion strategies for different robots operating under different assembly situations. Several extensions are also discussed.

The authors (1994) derived a quantitative measure of the ability of a camera setup to observe the changes in image features due to relative motion. This measure of motion perceptibility has many applications in evaluating a robot hand/eye setup with respect to the ease of achieving vision-based control, and steering away from singular-configurations. Motion perceptibility can be combined with the traditional notion of manipulability, into a composite perceptibility/manipulability measure. In this paper the authors demonstrate how this composite measure may be applied to a number of different problems involving relative hand/eye positioning and control. These problems include optimal camera placement, active camera trajectory planning, robot trajectory planning, and feature selection for visual servo control. The authors consider the general formulation of each of these problems, and several others, in terms of the motion perceptibility/manipulability measure and illustrate the solution for particular hand/eye configurations.

In this paper we introduce a new class of geometric robot motion planning problems that we call incremental problems. We also introduce the concept of incremental algorithms to solve this class of problems. As an example, we describe an incremental critical curve based exact cell decomposition algorithm for a line segment robot moving freely amidst polygonal obstacles. In the example, after computing an initial representation of the robot's free space, the algorithm maintains the representation as obstacles are moved between planning problems. The cost to maintain the representation is expected to be small relative to the cost of its initial construction.

Region-based image segmentation methods require some criterion for determining when to merge regions. This paper presents a novel approach by introducing a Bayesian probability of homogeneity in a general statistical context. The authors' approach does not require parameter estimation and is therefore particularly beneficial for cases in which estimation-based methods are most prone to error: when little information is contained in some of the regions and, therefore, parameter estimates are unreliable. The authors apply this formulation to three distinct parametric model families that have been used in past segmentation schemes: implicit polynomial surfaces, parametric polynomial surfaces, and Gaussian Markov random fields. The authors present results on a variety of real range and intensity images.>

Hierarchical approximate cell decomposition is a popular approach to the geometric robot motion planning problem. In many cases, the search effort expended at a particular iteration can be greatly reduced by exploiting the work done during previous iterations. In this paper, we describe how this exploitation of past computation can be effected by the use of a dynamically maintained single-source shortest paths tree. We embed a single-source shortest paths tree in the connectivity graph of the approximate representation of the robot configuration space. This shortest paths tree records the most promising path to each vertex in the connectivity graph from the vertex corresponding to the robot's initial configuration. At each iteration, some vertex in the connectivity graph is replaced with a new set of vertices, corresponding to a more detailed representation of the configuration space. Our new, dynamic algorithm is then used to update the single-source shortest paths tree to reflect these changes to the underlying connectivity graph.>

We introduce visual constraint surfaces as a mechanism to effectively exploit visual constraints in the synthesis of uncertainty-tolerant robot motion plans. We first show how object features, together with their projections onto a camera image plane, define a set of visual constraint surfaces. These visual constraint surfaces can be used to effect visual guarded and visual compliant motions. We then show how the backprojection approach to fine-motion planning can be extended to exploit visual constraints. Specifically, by deriving a configuration space representation of visual constraint surfaces, we are able to include visual constraint surfaces as boundaries of the directional backprojection. By examining the effect of visual constraints as a function of the direction of the commanded velocity, we are able to determine new criteria for critical velocity orientations, i.e. velocity orientations at which the topology of the directional backprojection might change.>

We present an integrated architecture for real-time planning and control of robot motions, for a robot operating in the presence of moving obstacles whose trajectories are not known a priori. The architecture comprises three control loops: an inner loop to linearize the robot dynamics, and two outer loops to implement the attractive and repulsive forces used by an artificial potential field motion planning algorithm. From a control theory perspective, our approach is unique in that the outer control loops are used to effect both desirable transient response and collision avoidance. From a motion planning perspective, our approach is unique in that the dynamic characteristics of both the robot and the moving obstacles are considered. Several simulations are presented that demonstrate the effectiveness of the planner/controller combination.>

In this paper, we present a new hybrid motion planner that is capable of exploiting previous planning episodes when confronted with new planning problems. Our approach is applicable when several (similar) problems are successively posed for the same static environment, or when the environment changes incrementally between planning episodes. At the heart of our system lie two low-level motion planners: a fast, but incomplete planner LOCAL, and a computationally costly (possibly resolution) complete planner GLOBAL. When a new planning problem is presented to our planner, an efficient meta-level planner MANAGER decomposes the problem into segments that are amenable to solution by LOCAL. This decomposition is made by exploiting a task graph, in which successful planning episodes have been recorded. In cases where the decomposition fails, GLOBAL is invoked. The key to our planner's success is a novel representation of solution trajectories, in which segments of collision-free paths are associated with the boundary of nearby obstacles. Thus we effectively combine the efficiency of one planner with the completeness of another to obtain a more efficient complete planner.>

Discusses the use of computer vision for real-time state estimation in feedback control systems. To this end, the authors construct a system for visual state estimation of simple state vectors and study the effects of various real-world disturbances on the state estimates. Simulations are performed using a detailed camera model to study the performance of an image plane position estimation algorithm for a single circular feature. Various disturbances, such as lens distortion, noise, defocus, and blurring are simulated and analyzed with respect to this estimation routine and visual state estimation in general.>

We present a method for analyzing and selecting time-optimal coordination strategies for n robots whose configurations are constrained to lie on a C-space roadmap (which could, for instance, represent a Voronoi diagram). We consider independent objective functionals, associated with each robot, together in a game-theoretic context in which maximal Nash equilibria represent the favorable strategies. Within this framework additional criteria, such as priority or the amount of sacrifice one robot makes, can be applied to select a particular equilibrium. An algorithm that determines all of the maximal Nash equilibria for a given problem is presented along with several computed examples for two and three robots.>

Defines a measure of "observability" of robot motion that can be used in evaluating a hand/eye set-up with respect to the ease of achieving vision-based control. This extends the analysis of "manipulability" of a robotic mechanism in Yoshikawa (1983) to incorporate the effect of visual features. The authors discuss how the observability measure can be applied for active camera placement and for robot trajectory planning to improve the visual servo control. The authors use the examples of a planar 2-DOF arm and a PUMA-type 3-DOF arm to show the variation of the observability and manipulability measure with respect to the relative position of the active camera.>

We consider the problem of determining robot manipulation plans when sensing and control uncertainties are specified as conditional probability densities. Traditional approaches are usually based on worst-case error analysis in a methodology known as preimage backchaining. We have developed a general framework for determining sensor-based robot plans by blending ideas from stochastic optimal control and dynamic game theory with traditional preimage backchaining concepts. We argue that the consideration of a precise loss (or performance) functional is crucial to determining and evaluating manipulation plans in a probabilistic setting. We consequently introduce a stochastic, performance preimage that generalizes previous preimage notions. We also present some optimal strategies for planar manipulation tasks that were computed by a dynamic programming-based algorithm.>

This paper introduces visual compliance, a new vision-based control scheme that lends itself to task-level specification of manipulation goals. Visual compliance is effected by a hybrid vision/position control structure. Specifically, the two degrees of freedom parallel to the image plane of a supervisory camera are controlled using visual feedback, and the remaining degree of freedom (perpendicular to the camera image plane) is controlled using position feedback provided by the robot joint encoders. With visual compliance, the motion of the end effector is constrained so that the tool center of the end effector maintains "contact" with a specified projection ray of the imaging system. This type of constrained motion can be exploited for grasping, parts mating, and assembly. The authors begin by deriving the projection equations for the vision system. They then derive equations used to position the manipulator prior to the execution of visual compliant motion. Following this, the authors derive the hybrid Jacobian matrix that is used to effect visual compliance. Experimental results are given for a number of scenarios, including grasping using visual compliance.>

A novel Bayesian approach to region merging is described. It directly uses statistical image models to determine the probability that the union of two regions is homogeneous, and does not require parameter estimation. This approach is particularly beneficial for cases in which the merging decision is most likely to be incorrect, i.e., when little information is contained in one or both of the regions and when parameter estimates are unreliable. The formulation is applied to the implicit polynomial surface model for range data, and texture models for intensity images.>

Clustering methods, which are frequently employed for region-based segmentation, are inherently metric based. A fundamental problem with an estimation-based criterion is that as the amount of information in a region decreases, the parameter estimates become extremely unreliable and incorrect decisions are likely to be made. It is shown that clustering need not be metric based. A rigorous region merging probability function is used. It makes use of all information available in the probability densities of a statistical image model. By using this probability function as a termination criterion it is possible to produce segmentations in which all region merges are performed above some level of confidence.>

The authors address a number of issues associated with visual servo control of robotic manipulators. They derive a set of projection equations that are used in the derivation of the Jacobian matrix for resolved-rate visual servo control. A calibration procedure that determines those parameters that appear in the projection equations is presented. Given the projection equations and calibration procedure, a set of equations is derived that can be used to initially position the manipulator at a specified perpendicular distance from the camera such that the tool center of the end effector projects onto a specified pixel on the image plane. A Jacobian matrix that is used to effect hybrid control of the manipulator is derived. Specifically, the two degrees of freedom parallel to the image plane of the camera are controlled using visual feedback, and the remaining degree of freedom is controlled using position feedback provided by the robot joint encoders.>

We present a motion planning/control system that deals with moving obstacles whose trajectories are not known a priori. An artificial potential field planner is tightly coupled with a robust inverse dynamic controller, allowing the robot to avoid obstacles in realtime while retaining the benefits of inverse dynamic control. Our implementation of the artificial potential field planner uses digital filtering techniques to shape the input signal to the inverse dynamic controller, so that system’s response to moving obstacles will depend, not only on the position of those obstacles, but also on their velocity relative to the robot. We prove stability along solution trajectories of the system in the absence of obstacles, and discuss stability issues that arise when obstacles are present.

GINKO, an integrated learning and planning system that has been applied to an autonomous mobile robot domain, is described. The goal of GINKO's learning system is to partition the robot's configuration space into regions in which actions exhibit a uniform qualitative behavior. This partitioning is performed by an inductive learning algorithm that classifies regions of the configuration space with regard to the effects of the robot's actions when executed in those regions. GINKO's learning is driven by its attempts to perform tasks. Thus, the learned effects of actions are directly applicable to normal system performance.>

A number of issues concerning the integration of visual and physical constraints for the synthesis and execution of error-tolerant motion strategies are addressed. Object features and their projections onto the image plane of a supervisory camera are used to define visual constraint surfaces. These surfaces can be directly used to enforce the following types of constrained motion: motion terminated on contact with a visual constraint surface, motion maintaining constant contact with a visual constraint surface, and motion that is simultaneously constrained by both visual and physical constraint surfaces. Preimage planning techniques are extended to the synthesis of motion strategies that exploit these types of motion.>

A description is given of SPAR, a task planner that has been implemented on a PUMA 762. SPAR is capable of formulating manipulation plans to meet specified assembly goals; these manipulation plans include grasping and regrasping operations if they are deemed necessary for successful completion of assembly. SPAR goes beyond classical AI planners in the sense that SPAR is capable of solving geometric goals associated with high-level symbolic goals. Consequently, if a high-level symbolic goals. Consequently, if a high-level symbolic goal is on (A,B), SPAR can also entertain the geometric conditions associated with such a goal. Therefore, a simple goal such as on (A,B) may or may not be found to be feasible depending on the kinematic constraints implied by the associated geometric conditions. SPAR has available to it a user-defined repertoire of actions for solving goals and associated with each action is an uncertainty precondition that defines the maximum uncertainty in the world description that would guarantee the successful execution of that action. SPAR has been implemented as a nonlinear constraint posting planner.>

An architecture for reasoning with uncertainty about the identities of objects in a scene is described. The main components of this architecture create and assign credibility to object hypotheses based on feature-match, object, relational, and aspect consistencies. The Dempster-Shafer formalism is used for representing uncertainty, so these credibilities are expressed as belief functions which are combined using Dempster's combination rule to yield the system's aggregate belief in each object hypothesis. One of the principal objections to the use of Dempster's rule is that its worst-case time complexity is exponential in the size of the hypothesis set. The structure of the hypothesis sets developed by this system allow for a polynomial implementation of the combination rule. Experimental results affirm the effectiveness of the method in assessing the credibility of candidate object hypotheses.>

An approach is presented for planning sensing strategies dynamically on the basis of the system's current best information about the world. The approach is for the system to propose a sensing operation automatically and then to determine the maximum ambiguity which might remain in the world description if that sensing operation were applied. The system then applies that sensing operation which minimizes this ambiguity. To do this, the system formulates object hypotheses and assesses its relative belief in those hypotheses to predict what features might be observed by a proposed sensing operation. Furthermore, since the number of sensing operations available to the system can be arbitrarily large, equivalent sensing operations are grouped together using a data structure that is based on the aspect graph. In order to measure the ambiguity in a set of hypotheses, the authors apply the concept of entropy from information theory. This allows them to determine the ambiguity in a hypothesis set in terms of the number of hypotheses and the system's distribution of belief among those hypotheses.>

The authors present an approach to planning sensing strategies in a robot workcell with multisensor capabilities. The system first forms an initial set of object hypotheses by using one of the sensors. Subsequently, the system reasons over different possibilities for selecting the next sensing operation, this being done in a manner so as to maximally disambiguate the initial set of hypotheses. The 'next sensing operation' is characterized by both the choice of the sensor and the viewpoint to be used. Aspect graph representation of objects plays a central role in the selection of the viewpoint, these representations being derived automatically by a solid modelling program.>

In this paper, we present FProlog, a programming language designed to act as the top level in a robot assembly system. FProlog is a logic programming language, with the ability to interface with LISP. This allows the use of a logic programming environment to construct assembly plans, while using LISP programs to interface with vision systems, world modeling systems, robot manipulators, etc. FProlog differs from hybrid logic programming languages, such as LOGLISP, in that FProlog may invoke functional programs as goals, and functional programs may invoke FProlog's inference engine. Also, FProlog differs from traditional robot assembly languages, such as AUTOPASS, in its generality, and therefore its ability to interface with many different subsystems. As a demonstration of the applicability of FProlog, we also present an FProlog program which is used as the top level in a robot assembly system which performs a version of the blocks world experiment.