We address the problem of stable and robust control of vehicles with lateral error dynamics for the application of lane keeping. Lane departure is the primary reason for half of the fatalities in road accidents, making the development of stable, adaptive and robust controllers a necessity. Any disturbance or uncertainty introduced to the steering-angle input can be catastrophic for the vehicle. Therefore, controllers must be developed to actively handle such uncertainties. In this work, we introduce a Neural$\mathcal{L}_1$Adaptive controller (Neural-L1) which learns the uncertainties in the lateral error dynamics of a front-steered Ackermann vehicle and guarantees stability and robustness. Our contributions are threefold: i) We extend the theoretical results for guaranteed stability and robustness of conventional$\mathcal{L}_1$Adaptive controllers to Neural-L1; ii) We implement a Neural-L1 for the lane keeping application which learns uncertainties in the dynamics accurately; iii) We evaluate the performance of Neural-L1 on a physics-based simulator, PyBullet, and conduct extensive real-world experiments with the FlTENTH platform to demonstrate superior reference trajectory tracking performance of Neural-L1 compared to other state-of-the-art controllers, in the presence of uncertainties. Our project page, including supplementary material and videos, can be found at https://mukhe027.github.io/Neural-Adaptive-Control/

We study the problem of sampling robot trajectories and introduce the notion of C-Uniformity. As opposed to the standard method of uniformly sampling control inputs (which lead to biased samples of the configuration space), C-Uniform trajectories are generated by control actions which lead to uniform sampling of the configuration space. After presenting an intuitive closed-form solution to generate C-Uniform trajectories for the 1D random-walker, we present a network-flow based optimization method to precompute action probabilities which lead to C-Uniform trajectories for general robot systems. We apply the notion of C-Uniformity to the design of Model Predictive Path Integral controllers. Through simulation experiments, we show that using C-Uniform trajectories significantly improvs the performance of MPPI-style controllers, achieving up to 40 % coverage performance gain compared to the best baseline. We demonstrate the practical applicability of our method with an implementation on a$1 / 10$th scale racer.

We study a pursuit-evasion game between two players with car-like dynamics and sensing limitations by formalizing it as a partially observable stochastic zero-sum game. The partial observability caused by the sensing constraints is particularly challenging. As an example, in a situation where the agents have no visibility of each other, they would need to extract information from their sensor coverage history to reason about potential locations of their opponents. However, keeping historical information greatly increases the size of the state space. To mitigate the challenges encountered with such partially observable problems, we develop a new learning-based method that encodes historical information to a belief state and uses it to generate agent actions. Through experiments we show that the learned strategies improve over existing multi-agent RL baselines by up to 16% in terms of capture rate for the pursuer. Additionally, we present experimental results showing that learned belief states are strong state estimators for extending existing game theory solvers and demonstrate our method’s competitiveness for problems where existing fully observable game theory solvers are computationally feasible. Finally, we deploy the learned policies on physical robots for a game between the F1TENTH and JetRacer platforms moving as fast as 2 m/s in indoor environments, showing that they can be executed on real-robots.

Sampling-based model predictive controllers generate trajectories by sampling control inputs from a fixed, simple distribution such as the normal or uniform distributions. This sampling method yields trajectory samples that are tightly clustered around a mean trajectory. This clustering behavior in turn, limits the exploration capability of the controller and reduces the likelihood of finding feasible solutions in complex environments. Recent work has attempted to address this problem by either reshaping the resulting trajectory distribution or increasing the sample entropy to enhance diversity and promote exploration. In our recent work, we introduced the concept of C-Uniform trajectory generation [1] which allows the computation of control input probabilities to generate trajectories that sample the configuration space uniformly. In this work, we first address the main limitation of this method: lack of scalability due to computational complexity. We introduce Neural C-Uniform, an unsupervised C-Uniform trajectory sampler that mitigates scalability issues by computing control input probabilities without relying on a discretized configuration space. Experiments show that Neural C-Uniform achieves a similar uniformity ratio to the original C-Uniform approach and generates trajectories over a longer time horizon while preserving uniformity. Next, we present CU-MPPI, which integrates Neural C-Uniform sampling into existing MPPI variants. We analyze the performance of CU-MPPI in simulation and real-world experiments. Our results indicate that in settings where the optimal solution has high curvature, CU-MPPI leads to drastic improvements in performance. Additionally, it performs as well as or better than baseline methods in dynamic environments. Additional results can be found at the project website.

The ability to capture rich representations of combinatorial structures has enabled the application of machine learning to tasks such as analysis and generation of floorplans, terrains, images, and animations. Recent work has primarily focused on understanding structures with well-defined features, neighborhoods, or underlying distance metrics, while those lacking such characteristics remain largely unstudied. Examples of these combinatorial structures can be found in polygons, where a small change in the vertex locations causes a significant rearrangement of the combinatorial structure, expressed as a visibility or triangulation graphs. Current representation learning approaches fail to capture structures without well-defined features and distance metrics. In this paper, we study the open problem of Visibility Reconstruction: Given a visibility graph $G$, construct a polygon $P$ whose visibility graph is $G$. We introduce $\textbf{VisDiff}$, a novel diffusion-based approach to generate polygon $P$ from the input visibility graph $G$. The main novelty of our approach is that, rather than generating the polygon's vertex set directly, we first estimate the signed distance function (SDF) associated with the polygon. The SDF is then used to extract the vertex location representing the final polygon. We show that going through the SDF allows $\textbf{VisDiff}$ to learn the visibility relationship much more effectively than generating vertex locations directly. In order to train $\textbf{VisDiff}$, we create a carefully curated dataset. We use this dataset to benchmark our method and achieve 26\% improvement in F1-Score over standard methods as well as state of the art approaches. We also provide preliminary results on the harder visibility graph recognition problem in which the input $G$ is not guaranteed to be a visibility graph. To demonstrate the applicability of VisDiff beyond visibility graphs, we extend it to the related combinatorial structure of triangulation graph. Lastly, leveraging these capabilties, we show that VisDiff can perform high-diversity sampling over the space of all polygons. In particular, we highlight its ability to perform both polygon-to-polygon interpolation and graph-to-graph interpolation, enabling diverse sampling across the polygon space.

Recently introduced ControlNet has the ability to steer the text-driven image generation process with geometric input such as 2D human pose, or edge representations. While ControlNet provides control over the geometric form of the instances in the generated image, it lacks the capability to dictate the visual appearance of each instance. We present FineControlNet to provide fine control over each instance's appearance while maintaining the pose control capability. Specifically, we develop and demonstrate FineControlNet with geometric control via human pose images and appearance control via instance-level text prompts. The spatial alignment of 2D poses and instance-specific text prompts in latent space enables the fine control of multiple instances. We evaluate the performance of FineControlNet with rigorous comparison against state-of-the-art pose-conditioned text-to-image diffusion models. FineControlNet achieves superior performance in generating high quality images that follow instance-specific controls. We will release the code and the dataset.

Frost accumulation on refrigerator evaporator coils is a significant source of wasted energy. While automatic de-frosting is a standard feature on modern refrigerators, current commercial solutions use heuristics to determine the frequency of heating cycles, leading to a sub-optimal defrosting routine. The majority of previous defrosting research incorporates cameras or microwave technology to better inform defrost algorithms of frost accumulation, however, these methods are both financially and computationally expensive. In this paper, we propose a low-cost frost detection system using ultrasonic resonance of piezoelectric sensors. We addressed the financial and computational cost challenges by using low-cost sensors and basic circuit components to replace software complexity. Our frost detection system was evaluated extensively in a Samsung refrigerator, resulting in a frost detection accuracy of 99.7%. We believe our solution can be further used for downstream refrigerator control cycle optimizations to achieve improved energy efficiency.

We study the problem of aligning a video that captures a local portion of an environment to the 2D LiDAR scan of the entire environment. We introduce a method (VioLA) that starts with building a semantic map of the local scene from the image sequence, then extracts points at a fixed height for registering to the LiDAR map. Due to reconstruction errors or partial coverage of the camera scan, the reconstructed semantic map may not contain sufficient information for registration. To address this problem, VioLA makes use of a pre-trained text-to-image inpainting model paired with a depth completion model for filling in the missing scene content in a geometrically consistent fashion to support pose registration. We evaluate VioLA on two real-world RGB-D benchmarks, as well as a self-captured dataset of a large office scene. Notably, our proposed scene completion module improves the pose registration performance by up to 20%.

This paper presents a method to learn hand-object interaction prior for reconstructing a 3D hand-object scene from a single RGB image. The inference as well as training-data generation for 3D hand-object scene reconstruction is challenging due to the depth ambiguity of a single image and occlusions by the hand and object. We turn this challenge into an opportunity by utilizing the hand shape to constrain the possible relative configuration of the hand and object geometry. We design a generalizable implicit function, HandNeRF, that explicitly encodes the correlation of the 3D hand shape features and 2D object features to predict the hand and object scene geometry. With experiments on real-world datasets, we show that HandNeRF can reconstruct hand-object scenes of novel grasp configurations more accurately than comparable methods. Moreover, we demonstrate that object reconstruction from HandNeRF ensures more accurate execution of downstream tasks, such as grasping for robotic hand-over.

A robot in a human-centric environment needs to account for the human’s intent and future motion in its task and motion planning to ensure safe and effective operation. This requires symbolic reasoning about probable future actions and the ability to tie these actions to specific locations in the physical environment. While one can train behavioral models capable of predicting human motion from past activities, this approach requires large amounts of data to achieve acceptable long-horizon predictions. More importantly, the resulting models are constrained to specific data formats and modalities. Moreover, connecting predictions from such models to the environment at hand to ensure the applicability of these predictions is an unsolved problem. We present a system that utilizes a Large Language Model (LLM) to infer a human’s next actions from a range of modalities without fine-tuning. A novel aspect of our system that is critical to robotics applications is that it links the predicted actions to specific locations in a semantic map of the environment. Our method leverages the fact that LLMs, trained on a vast corpus of text describing typical human behaviors, encode substantial world knowledge, including probable sequences of human actions and activities. We demonstrate how these localized activity predictions can be incorporated in a human-aware task planner for an assistive robot to reduce the occurrences of undesirable human-robot interactions by 29.2% on average.

General scene reconstruction refers to the task of estimating the full 3D geometry and texture of a scene containing previously unseen objects. In many practical applications such as AR/VR, autonomous navigation, and robotics, only a single view of the scene may be available, making the scene reconstruction task challenging. In this paper, we present a method for scene reconstruction by structurally breaking the problem into two steps: rendering novel views via inpainting and 2D to 3D scene lifting. Specifically, we leverage the generalization capability of large visual language models (DALL•E 2) to inpaint the missing areas of scene color images rendered from different views. Next, we lift these inpainted images to 3D by predicting normals of the inpainted image and solving for the missing depth values. By predicting for normals instead of depth directly, our method allows for robustness to changes in depth distributions and scale. With rigorous quantitative evaluation, we show that our method outperforms multiple baselines while providing generalization to novel objects and scenes. Code and data is available at https://samsunglabs.github.io/RIC-project-page/.

We consider the problem of closed-loop robotic grasping and present a novel planner which uses Visual Feedback and an uncertainty-aware Adaptive Sampling strategy (VFAS) to close the loop. At each iteration, our method VFAS-Grasp builds a set of candidate grasps by generating random perturbations of a seed grasp. The candidates are then scored using a novel metric which combines a learned grasp-quality estimator, the uncertainty in the estimate and the distance from the seed proposal to promote temporal consistency. Additionally, we present two mechanisms to improve the efficiency of our sampling strategy: We dynamically scale the sampling region size and number of samples in it based on past grasp scores. We also leverage a motion vector field estimator to shift the center of our sampling region. We demonstrate that our algorithm can run in real time (20 Hz) and is capable of improving grasp performance for static scenes by refining the initial grasp proposal. We also show that it can enable grasping of slow moving objects, such as those encountered during human to robot handover. Video: https://youtu.be/8DRe2OFlf7o

A good representation of a large, complex mobile robot workspace must be space-efficient yet capable of encoding relevant geometric details. When exploring unknown environments, it needs to be updatable incrementally in an online fashion. We introduce HIO-SDF, a new method that represents the environment as a Signed Distance Field (SDF). State of the art representations of SDFs are based on either neural networks or voxel grids. Neural networks are capable of representing the SDF continuously. However, they are hard to update incrementally as neural networks tend to forget previously observed parts of the environment unless an extensive sensor history is stored for training. Voxel-based representations do not have this problem but they are not space-efficient especially in large environments with fine details. HIO-SDF combines the advantages of these representations using a hierarchical approach which employs a coarse voxel grid that captures the observed parts of the environment together with high-resolution local information to train a neural network. HIO-SDF achieves a 46% lower mean global SDF error across all test scenes than a state of the art continuous representation, and a 30% lower error than a discrete representation at the same resolution as our coarse global SDF grid. Videos and code are available at: https://samsunglabs.github.io/HIO-SDF-project-page/

In the robot follow-ahead task, a mobile robot is tasked to maintain its relative position in front of a moving human actor while keeping the actor in sight. To accomplish this task, it is important that the robot understand the full 3D pose of the human (since the head orientation can be different than the torso) and predict future human poses so as to plan accordingly. This prediction task is especially tricky in a complex environment with junctions and multiple corridors. In this work, we address the problem of forecasting the full 3D trajectory of a human in such environments. Our main insight is to show that one can first predict the 2D trajectory and then estimate the full 3D trajectory by conditioning the estimator on the predicted 2D trajectory. With this approach, we achieve results comparable or better than the state-of-the-art methods three times faster. As part of our contribution, we present a new dataset where, in contrast to existing datasets, the human motion is in a much larger area than a single room. We also present a complete robot system that integrates our human pose forecasting network on the mobile robot to enable real-time robot follow-ahead and present results from real-world experiments in multiple buildings on campus. Our project page, including supplementary material and videos, can be found at: https://qingyuan-jiang.github.io/iros2024_poseForecasting/

Correspondence search is an essential step in rigid point cloud registration algorithms. Most methods maintain a single correspondence at each step and gradually remove wrong correspondances. However, building one-to-one correspondence with hard assignments is extremely difficult, especially when matching two point clouds with many locally similar features. This paper proposes an optimization method that retains all possible correspondences for each keypoint when matching a partial point cloud to a complete point cloud. These uncertain correspondences are then gradually updated with the estimated rigid transformation by considering the matching cost. More-over, we propose a new point feature descriptor that measures the similarity between local point cloud regions. Extensive experiments show that our method outperforms the state-of-the-art (SoTA) methods even when matching different objects within the same category. Notably, our method outperforms the SoTA methods when registering real-world noisy depth images to a template shape by up to 20% performance.

We study the problem of generating control laws for systems with unknown dynamics. Our approach is to represent the controller and the value function with neural networks, and to train them using loss functions adapted from the Hamilton-Jacobi-Bellman (HJB) equations. In the absence of a known dynamics model, our method first learns the state transitions from data collected by interacting with the system in an offline process. The learned transition function is then integrated to the HJB equations and used to forward simulate the control signals produced by our controller in a feedback loop. In contrast to trajectory optimization methods that optimize the controller for a single initial state, our controller can generate near-optimal control signals for initial states from a large portion of the state space. Compared to recent model-based reinforcement learning algorithms, we show that our method is more sample efficient and trains faster by an order of magnitude. We demonstrate our method in a number of tasks, including the control of a quadrotor with 12 state variables.

The choice of a grasp plays a critical role in the success of downstream manipulation tasks. Consider a task of placing an object in a cluttered scene; the majority of possible grasps may not be suitable for the desired placement. In this paper, we study the synergy between the picking and placing of an object in a cluttered scene to develop an algorithm for task-aware grasp estimation. We present an object-centric action space that encodes the relationship between the geometry of the placement scene and the object to be placed in order to provide placement affordance maps directly from perspective views of the placement scene. This action space enables the computation of a one-to-one mapping between the placement and picking actions allowing the robot to generate a diverse set of pick-and-place proposals and to optimize for a grasp under other task constraints such as robot kinematics and collision avoidance. With experiments both in simulation and on a real robot we demonstrate that with our method, the robot is able to successfully complete the task of placement-aware grasping with over 89 % accuracy in such a way that generalizes to novel objects and scenes.

Recent advances in robotic mapping enable robots to use both semantic and geometric understanding of their surroundings to perform complex tasks. Current methods are optimized for reconstruction quality, but they do not provide a measure of how certain they are of their outputs. Therefore, algorithms that use these maps do not have a way of assessing how much they can trust the outputs. We present a mapping approach that unifies semantic information and shape completion inferred from RGBD images and computes confidence scores for its predictions. We use a Gaussian Process (GP) classification model to merge confidence scores (if available) for the given information. A novel aspect of our method is that we lift the measurement to a learned metric space over which the GP parameters are learned. After training, we can evaluate the uncertainty of objects' completed shapes with their semantic information. We show that our approach can achieve more accurate predictions than a classic GP model and provide robots with the flexibility to decide whether they can trust the estimate at a given location using the confidence scores.

We introduce a new route-finding problem which considers perception and travel costs simultaneously. Specifically, we consider the problem of finding the shortest tour such that all objects of interest can be detected successfully. To represent a viable detection region for each object, we propose to use an entropy-based viewing score that generates a diameter-bounded region as a viewing neighborhood. We formulate the detection-based trajectory planning problem as a stochastic traveling salesperson problem with neighborhoods and propose a center-visit method that obtains an approximation ratio of$O(\frac{D_{max}}{D_{min}})$for disjoint regions. For non-disjoint regions, our method -provides a novel finite detour in 3D, which utilizes the region's minimum curvature property. Finally, we show that our method can generate efficient trajectories compared to a baseline method in a photo-realistic simulation environment.

Robot end effectors with proximity detection and contact sensing capabilities can reactively position the gripper to align objects and ensure successful grasps. In this paper, we introduce SonicFinger, an acoustic aura based sensing system capable of full-surface pre-touch and contact sensing. A single piezoelectric transducer embedded within a novel 3D printed finger is excited using a monotone to create an acoustic aura encompassing the finger; this enables pre-touch sensing and gripper alignment, while changes in finger-transducer acoustic coupling indicate contact. SonicFinger is low-cost, compact, and easy to manufacture and assemble. Sensing capabilities are evaluated using a set of objects with various physical properties such as optical reflectivity, dielectric constants, mechanical properties, and acoustic absorption. A dataset with over 8,000 proximity and contact events is collected. Our system shows a pre-touch detection true positive rate (TPR) of 92.4% and a true negative rate (TNR) of 95.3%. Contact detection experiments show a TPR of 93.7% and a TNR of 98.7%. Furthermore, pretouch detection information from Sonic Finger is used to adjust the robot grippers pose to align a target object at the center of both fingers.

In this paper, we present a realtime method for simultaneous object-level scene understanding and grasp prediction. Specifically, given a single RGBD image of a scene, our method localizes all the objects in the scene and for each object, it generates the following: full 3D shape, scale, pose with respect to the camera frame, and a dense set of feasible grasps. The main advantage of our method is its computation speed as it avoids sequential perception and grasp planning. With detailed quantitative analysis of reconstruction quality and grasp accuracy, we show that our method delivers competitive performance compared to the state-of-the-art methods, while providing fast inference at 30 frames per second speed.

In this paper, we address the problem of system identification and control of a front-steered vehicle which abides by the Ackermann geometry constraints. This problem arises naturally for on-road and off-road vehicles that require reliable system identification and basic feedback controllers for various applications such as lane keeping and way-point navigation. Traditional system identification requires expensive equipment and is time consuming. In this work we explore the use of differentiable physics for system identification and controller design and make the following contributions: i) We develop a differentiable physics simulator (DPS) to provide a method for the system identification of front-steered class of vehicles whose system parameters are learned using a gradient-based method; ii) We provide results for our gradient-based method that exhibit better sample efficiency in comparison to other gradient-free methods; iii) We validate the learned system parameters by implementing a feedback controller to demonstrate stable lane keeping performance on a real front-steered vehicle, the F1TENTH; iv) Further, we provide results exhibiting comparable lane keeping behavior for system parameters learned using our gradient-based method with lane keeping behavior of the actual system parameters of the F1TENTH.

Contact sensing and localization capabilities that mimic human skin are highly desirable for robots. In this paper, we introduce AcouSkin, an acoustic wave based full surface contact localization system. Acoustic waves produced by piezoelectric transceivers using a monotone are coupled to surfaces turning them into an active sensor. Our system leverages information from four piezoelectric transceivers mounted on the surface of an acrylic sheet and vacuum cleaner robot bumper to localize contacts to 18 unique segments. We first characterize acoustic wave propagation based on signal and material properties and then propose hardware and software methods to realize full surface contact localization. Our results show that AcouSkin can reliably localize contact on a flat acrylic sheet with 18 uniformly spaced locations across a 54cm length with mean absolute error (MAE) of ≤ 1 locations using maximum likelihood estimator (MLE) and multilayer perceptron (MLP) models. On the vacuum cleaner robot bumper AcouSkin shows a zero MAE. Further, the system is also able to localize contacts made using forces as low as 2N (Newtons) and as high as 20N. Overall, AcouSkin provides full surface contact localization while requiring minimal instrumentation with easy deployment on real-world robots.

In this paper, we present AmbiSense, an acoustic field based sensing system that performs proximity detection and bearing estimation for safer physical human-robot interactions. A single low cost piezoelectric transducer is used to setup this novel acoustic sensing modality to create a blindspot-free sound field engulfing a robot arm. Two detection algorithms leveraging spectral information from reflected audio waves of objects entering the acoustic field are proposed to infer object presence and bearing. We also present a new receiver structure which improves signal to noise ratio (SNR). AmbiSense is paired with a collision avoidance inverse kinematic solver for real world deployment on a Kinova Gen3 robot. Validation is performed using ten test objects generating 2000 proximity and bearing estimation events in real world settings, we show that AmbiSense detects proximity with 93.8% sensitivity and 96.6 % specificity. It estimates bearing and maps it to three zones on a robot link with 100% sensitivity and specificity, while using fewer sensors than state of the art methods for similar coverage.

We introduce Reactive Action and Motion Planner (RAMP), which combines the strengths of sampling-based and reactive approaches for motion planning. In essence, RAMP is a hierarchical approach where a novel variant of a Model Predictive Path Integral (MPPI) controller is used to generate trajectories which are then followed asynchronously by a local vector field controller. We demonstrate, in the context of a table clearing application, that RAMP can rapidly find paths in the robot's configuration space, satisfy task and robot-specific constraints, and provide safety by reacting to static or dynamically moving obstacles. RAMP achieves superior performance through a number of key innovations: we use Signed Distance Function (SDF) representations directly from the robot configuration space, both for collision checking and reactive control. The use of SDFs allows for a smoother definition of collision cost when planning for a trajectory, and is critical in ensuring safety while following trajectories. In addition, we introduce a novel variant of MPPI which, combined with the safety guarantees of the vector field trajectory follower, performs incremental real-time global trajectory planning. Simulation results establish that our method can generate paths that are comparable to traditional and state-of-the-art approaches in terms of total trajectory length while being up to 30 times faster. Real-world experiments demonstrate the safety and effectiveness of our approach in challenging table clearing scenarios. Videos and code are available at: https://samsunglabs.github.io/RAMP-project-page/

In this work, we present a method to estimate the planar mass distribution of a rigid object through robotic interactions and force/torque feedback. This is a challenging problem because of the complexity of modeling physical dynamics and the action dependencies across the model parameters. We propose a sequential estimation strategy combined with a set of robot action selection rules based on the analytical formulation of a discrete-time dynamics model. To evaluate the performance of our approach, we also manufactured re-configurable block objects that allow us to modify the object mass distribution while having access to the ground truth values. We compare our approach against multiple baselines and show that it can estimate the mass distribution with around 10% error, while the baselines have errors ranging from 18% to 68%.

Reconstructing the 3D pose of a person in metric scale from a single view image is a geometrically ill-posed problem. For example, we can not measure the exact distance of a person to the camera from a single view image without additional scene assumptions (e.g., known height). Existing learning based approaches circumvent this issue by reconstructing the 3D pose up to scale. However, there are many applications such as virtual telepresence, robotics, and augmented reality that require metric scale reconstruction. In this paper, we show that audio signals recorded along with an image, provide complementary information to reconstruct the metric 3D pose of the person. The key insight is that as the audio signals traverse across the 3D space, their interactions with the body provide metric information about the body's pose. Based on this insight, we introduce a time-invariant transfer function called pose kernel-the impulse response of audio signals induced by the body pose. The main properties of the pose kernel are that (1) its envelope highly correlates with 3D pose, (2) the time response corresponds to arrival time, indicating the metric distance to the microphone, and (3) it is invariant to changes in the scene geometry configurations. Therefore, it is readily generalizable to unseen scenes. We design a multistage 3D CNN that fuses audio and visual signals and learns to reconstruct 3D pose in a metric scale. We show that our multi-modal method produces accurate metric reconstruction in realworld scenes, which is not possible with state-of-the-art lifting approaches including parametric mesh regression and depth regression.

Humans have the ability to pour various media, both liquid and granular, to desired ends in various containers. We do this by using multiple senses simultaneously in a constant feedback loop to complete a pouring task. Combining multiple sensing modalities, similar to humans, could aid in robotic pouring control outside of a structured or industrial setting. We present a multi-sensory pouring dataset consisting of human pouring demonstrations of various granular media, coupled with two multi-sensory networks that estimate pouring rate and pouring average height. For both pouring metrics, a combined input of audio and visual data provides a lower median error than either the audio network or visual network. The multi-sensory network achieves a median error of 6.4 mm for average height estimation and 0.06 N/s for pouring rate estimation.

As service robots begin to be deployed to assist humans, it is important for them to be able to perform a skill as ubiquitous as pouring. Specifically, we focus on the task of pouring an exact amount of water without any environmental instrumentation, that is, using only the robot's own sensors to perform this task in a general way robustly. In our approach we use a simple PID controller which uses the measured change in weight of the held container to supervise the pour. Unlike previous methods which use specialized force-torque sensors at the robot wrist, we use our robot joint torque sensors and investigate the added benefit of tactile sensors at the fingertips. We train three estimators from data which regress the poured weight out of the source container and show that we can accurately pour within 10 ml of the target on average while being robust enough to pour at novel locations and with different grasps on the source container.

We study a semantic SLAM problem where a robot is tasked with autonomous weeding under the corn canopy. The goal is to detect corn stalks and localize them in a global coordinate frame. This is a challenging scenario for existing algorithms because there is very little space between the camera and the plants, and the camera motion is primarily restricted to be along the row. To overcome these challenges, we present a multi-camera system where a side camera (facing the plants) is used for detection, whereas front and back cameras are used for motion estimation. Next, we show how semantic features in the environment (corn stalks, ground, and crop planes) can be used to develop a robust semantic SLAM solution and present results from field trials performed throughout the growing season across various cornfields.

Being able to grasp objects is a fundamental component of most robotic manipulation systems. In this paper, we present a new approach to simultaneously reconstruct a mesh and a dense grasp quality map of an object from a depth image. At the core of our approach is a novel camera-centric object representation called the “object shell” which is composed of an observed “entry image” and a predicted “exit image”. We present an image-to-image residual ConvNet architecture in which the object shell and a grasp-quality map are predicted as separate output channels. The main advantage of the shell representation and the corresponding neural network architecture, ShellGrasp-Net, is that the input-output pixel correspondences in the shell representation are explicitly represented in the architecture. We show that this coupling yields superior generalization capabilities for object reconstruction and accurate grasp quality estimation implicitly considering the object geometry. Our approach yields an efficient dense grasp quality map and an object geometry estimate in a single forward pass. Both of these outputs can be used in a wide range of robotic manipulation applications. With rigorous experimental validation, both in simulation and on a real setup, we show that our shell-based method can be used to generate precise grasps and the associated grasp quality with over 90% accuracy. Diverse grasps computed on shell reconstructions allow the robot to select and execute grasps in cluttered scenes with more than 93% success rate.

One of the challenging input settings for visual servoing is when the initial and goal camera views are far apart. Such settings are difficult because the wide baseline can cause drastic changes in object appearance and cause occlusions. This paper presents a novel self-supervised visual servoing method for wide baseline images which does not require 3D ground truth supervision. Existing approaches that regress absolute camera pose with respect to an object require 3D ground truth data of the object in the forms of 3D bounding boxes or meshes. We learn a coherent visual representation by leveraging a geometric property called 3D equivariance—the representation is transformed in a predictable way as a function of 3D transformation. To ensure that the feature-space is faithful to the underlying geodesic space, a geodesic preserving constraint is applied in conjunction with the equivariance. We design a Siamese network that can effectively enforce these two geometric properties without requiring 3D supervision. With the learned model, the relative transformation can be inferred simply by following the gradient in the learned space and used as feedback for closed-loop visual servoing. Our method is evaluated on objects from the YCB dataset, showing meaningful outperformance on a visual servoing task, or object alignment task with respect to state-of-the-art approaches that use 3D supervision. Ours yields more than 35% average distance error reduction and more than 90% success rate with 3cm error tolerance.

This paper presents a Dynamic Vision Sensor (DVS) based system for reasoning about high-speed motion. As a representative scenario we consider a robot at rest, reacting to a small, fast approaching object at speeds higher than 15 m/s. Since conventional image sensors at typical frame rates observe such an object for only a few frames, estimating the underlying motion presents a considerable challenge for standard computer vision systems and algorithms. We present a method motivated by how animals such as insects solve this problem with their relatively simple vision systems.Our solution takes the event stream from a DVS and first encodes the temporal events with a set of causal exponential filters across multiple time scales. We couple these filters with a Convolutional Neural Network (CNN) to efficiently extract relevant spatiotemporal features. The combined network learns to output both the expected time to collision of the object, as well as the predicted collision point on a discretized polar grid. These critical estimates are computed with minimal delay by the network in order to react appropriately to the incoming object. We highlight our system’s results with a toy dart moving at 23.4 m/s with a 24.73° error in θ, 18.4 mm average discretized radius prediction error, and 25.03% median time to collision prediction error.

This paper presents c2g-HOF networks which learn to generate cost-to-go functions for manipulator motion planning. The c2g-HOF architecture consists of a cost-to-go function over the configuration space represented as a neural network (c2g-network) as well as a Higher Order Function (HOF) network which outputs the weights of the c2g-network for a given input workspace. Both networks are trained end-to-end in a supervised fashion using costs computed from traditional motion planners. Once trained, c2g-HOF can generate a smooth and continuous cost-to-go function directly from workspace sensor inputs (represented as a point cloud in 3D or an image in 2D). At inference time, the weights of the c2g-network are computed very efficiently and near-optimal trajectories are generated by simply following the gradient of the cost-to-go function.We compare c2g-HOF with traditional planning algorithms for various robots and planning scenarios. The experimental results indicate that planning with c2g-HOF is significantly faster than other motion planning algorithms, resulting in orders of magnitude improvement when including collision checking. Furthermore, despite being trained from sparsely sampled trajectories in configuration space, c2g-HOF generalizes to generate smoother, and often lower cost, trajectories. We demonstrate cost-to-go based planning on a 7 DoF manipulator arm where motion planning in a complex workspace requires only 0.13 seconds for the entire trajectory.

In this work, we focus on mobile robot navigation in indoor environments where occlusions and field-of-view limitations hinder onboard sensing capabilities. We show that the footprint of a camera mounted on a robot can be drastically improved using learning-based approaches. Specifically, we consider the task of building an occupancy map for autonomous navigation of a robot equipped with a depth camera. In our approach, a local occupancy map is first computed using measurements from the camera directly. Afterwards, an inpainting network adds further information, the occupancy probabilities of unseen grid cells, to the map. A novel aspect of our approach is that rather than direct supervision from ground truth, we combine the information from a second camera with a better field-of-view for supervision. The training focuses on predicting extensions of the sensed data. To test the effectiveness of our approach, we use a robot setup with a single camera placed at 0.5m above the ground. We compare the navigation performance using raw maps from only this camera’s input (baseline) versus using inpainted maps augmented with our network. Our method outperforms the baseline approach even in completely new environments not included in the training set and can yield 21% shorter paths than the baseline approach. A real-time implementation of our method on a mobile robot is also tested in home and office environments.

We present a novel approach to robotic grasp planning using both a learned grasp proposal network and a learned 3D shape reconstruction network. Our system generates 6-DOF grasps from a single RGB-D image of the target object, which is provided as input to both networks. By using the geometric reconstruction to refine the candidate grasp produced by the grasp proposal network, our system is able to accurately grasp both known and unknown objects, even when the grasp location on the object is not visible in the input image.This paper presents the network architectures, training procedures, and grasp refinement method that comprise our system. Experiments demonstrate the efficacy of our system at grasping both known and unknown objects (91% success rate in a physical robot environment, 84% success rate in a simulated environment). We additionally perform ablation studies that show the benefits of combining a learned grasp proposal with geometric reconstruction for grasping, and also show that our system outperforms several baselines in a grasping task.

Learning object manipulation is a critical skill for robots to interact with their environment. Even though there has been significant progress in robotic manipulation of rigid objects, interacting with non-rigid objects remains challenging for robots. In this work, we introduce velcro peeling as a new application for robotic manipulation of non-rigid objects in complex environments. We present a method of learning force-based manipulation from noisy and incomplete sensor inputs in partially observable environments by modeling long term dependencies between measurements with a multi-step deep recurrent network. We present experiments on a real robot to show the necessity of modeling these long term dependencies and validate our approach in simulation and robot experiments. Our results show that using tactile input enables the robot to overcome geometric uncertainties present in the environment with high fidelity in ∼ 90% of all cases, outperforming the baselines by a large margin.

We study the problem of pursuit-evasion for a single pursuer and an evader in polygonal environments where the players have visibility constraints. The pursuer is tasked with catching the evader as quickly as possible while the evader tries to avoid being captured. We formalize this problem as a zero-sum game where the players have private observations and conflicting objectives.One of the challenging aspects of this game is due to limited visibility. When a player, for example, the pursuer does not see the evader, it needs to reason about all possible locations of the evader. This causes an exponential increase in the size of the state space as compared to the arena size. To overcome the challenges associated with large state spaces, we introduce a new learning-based method that compresses the game state and uses it to plan actions for the players. The results indicate that our method outperforms the existing reinforcement learning methods, and performs competitively against the current state-of-the-art randomized strategy in complex environments.

This paper presents a supervised learning method to generate continuous cost-to-go functions of non-holonomic systems directly from the workspace description. Supervision from informative examples reduces training time and improves network performance. The manifold representing the optimal trajectories of a non-holonomic system has high-curvature regions which can not be efficiently captured with uniform sampling. To address this challenge, we present an adaptive sampling method which makes use of sampling based planners along with local, closed-form solutions to generate training samples. The cost-to-go function over a specific workspace is represented as a neural network whose weights are generated by a second, higher order network. The networks are trained in an end-to-end fashion. In our previous work, this architecture was shown to successfully learn to generate the cost-to-go functions of holonomic systems using uniform sampling. In this work, we show that uniform sampling fails for non-holonomic systems. However, with the proposed adaptive sampling methodology, our network can generate near-optimal trajectories for non-holonomic systems while avoiding obstacles. Experiments show that our method is two orders of magnitude faster compared to traditional approaches in cluttered environments.

Images of heavily occluded objects in cluttered scenes, such as fruit clusters in trees, are hard to segment. To further retrieve the 3D size and 6D pose of each individual object in such cases, bounding boxes are not reliable from multiple views since only a little portion of the object's geometry is captured. We introduce the first CNN-based ellipse detector, called Ellipse R-CNN, to represent and infer occluded objects as ellipses. We first propose a robust and compact ellipse regression based on the Mask R-CNN architecture for elliptical object detection. Our method can infer the parameters of multiple elliptical objects even they are occluded by other neighboring objects. For better occlusion handling, we exploit refined feature regions for the regression stage, and integrate the U-Net structure for learning different occlusion patterns to compute the final detection score. The correctness of ellipse regression is validated through experiments performed on synthetic data of clustered ellipses. We further quantitatively and qualitatively demonstrate that our approach outperforms the state-of-the-art model (i.e., Mask R-CNN followed by ellipse fitting) and its three variants on both synthetic and real datasets of occluded and clustered elliptical objects.

In this work, we present a hardware-efficient architecture for pedestrian detection with neuromorphic Dynamic Vision Sensors (DVSs), asynchronous camera sensors that report discrete changes in light intensity. These imaging sensors have many advantages compared to traditional frame-based cameras, such as increased dynamic range, lower bandwidth requirements, and higher sampling frequency with lower power consumption. Our architecture is composed of two main components: an event filtering stage to denoise the input image stream followed by a low-complexity neural network. For the first stage, we use a novel point-process filter (PPF) with an adaptive temporal windowing scheme that enhances classification accuracy. The second stage implements a hardware-efficient Binary Neural Network (BNN) for classification. To demonstrate the reduction in complexity achieved by our architecture, we showcase a Field-Programmable Gate Array (FPGA) implementation of the entire system which obtains a 86& reduction in latency compared to current neural network floating-point architectures.

We address the problem of reconstructing a high-resolution surface representing an object from a single image. We present Surface HOF, which takes an image of an object as input and generates a mapping function for surface generation. The mapping function takes samples from a canonical domain and maps each sample to a local tangent plane on the 3D reconstruction of the object. By efficiently learning a continuous mapping function, the surface can be generated at arbitrary resolution in contrast to other methods which generate fixed resolution outputs. Experiments show that Surface HOF is more accurate and uses more efficient representations than other state of the art methods for surface reconstruction. Surface HOF is also easier to train: it requires minimal input pre-processing and output post-processing and generates surface representations that are more parameter efficient. Its accuracy and convenience make Surface HOF an appealing method for single image reconstruction.

We consider the problem of planning views for a robot to acquire images of an object for visual inspection and reconstruction. In contrast to offline methods which require a 3D model of the object as input or online methods which rely on only local measurements, our method uses a neural network which encodes shape information for a large number of objects. We build on recent deep learning methods capable of generating a complete 3D reconstruction of an object from a single image. Specifically, in this work, we extend a recent method which uses Higher Order Functions (HOF) to represent the shape of the object. We present a new generalization of this method to incorporate multiple images as input and establish a connection between visibility and reconstruction quality. This relationship forms the foundation of our view planning method where we compute viewpoints to visually cover the output of the multiview HOF network with as few images as possible. Experiments indicate that our method provides a good compromise between online and offline methods: Similar to online methods, our method does not require the true object model as input. In terms of number of views, it is much more efficient. In most cases, its performance is comparable to the optimal offline case even on object classes the network has not been trained on.

Collision detection is critical for safe robot operation in the presence of humans. Acoustic information originating from collisions between robots and objects provides opportunities for fast collision detection and localization; however, audio information from microphones on robot manipulators needs to be robustly differentiated from motors and external noise sources. In this paper, we present Panotti, the first system to efficiently detect and localize on-robot collisions using low-cost microphones. We present a novel algorithm that can localize the source of a collision with centimeter level accuracy and is also able to reject false detections using a robust spectral filtering scheme. Our method is scalable, easy to deploy, and enables safe and efficient control for robot manipulator applications. We implement and demonstrate a prototype that consists of 8 miniature microphones on a 7 degree of freedom (DOF) manipulator to validate our design. Extensive experiments show that Panotti realizes near perfect on-robot true positive collision detection rate with almost zero false detections even in high noise environments. In terms of accuracy, it achieves an average localization error of less than 3.8 cm under various experimental settings.

Many robotic coverage applications involve detection of spatially distributed targets, followed by path planning to visit them for service. In these applications, the performance of the detection algorithm can have profound effect on planning decisions and costs. Range of operation, in both space and time, for robots is typically finite over a single mission and is a common constraint that needs to be accounted for in decision making. Misclassification may result in wastage of resources and can even jeopardize the completion of a mission if the length of a path extends beyond the range of the robot. In this work, we develop techniques on the computation of planning-aware classification thresholds. We discuss two versions that compute binary classification thresholds as a function of planning budget and detection accuracy. We present an implementation of our methods in path planning applications for an autonomous mower and show results on real and simulated data. Our method allows upto 25% improvement in coverage as compared to standard thresholding methods.

Novel View Synthesis (NVS) is concerned with synthesizing views under camera viewpoint transformations from one or multiple input images. NVS requires explicit reasoning about 3D object structure and unseen parts of the scene to synthesize convincing results. As a result, current approaches typically rely on supervised training with either ground truth 3D models or multiple target images. We propose Continuous Object Representation Networks (CORN), a conditional architecture that encodes an input image's geometry and appearance that map to a 3D consistent scene representation. We can train CORN with only two source images per object by combining our model with a neural renderer. A key feature of CORN is that it requires no ground truth 3D models or target view supervision. Regardless, CORN performs well on challenging tasks such as novel view synthesis and single-view 3D reconstruction and achieves performance comparable to state-of-the-art approaches that use direct supervision. For up-to-date information, data, and code, please see our project page: https://nicolaihaeni.github.io/corn/.

In this paper, we study the Online Network Formation Problem (ONFP) for a mobile multi-robot system. Consider a group of robots with a bounded communication range operating in a large open area. One of the robots has a piece of information which has to be propagated to all other robots. What strategy should the robots pursue to disseminate the information to the rest of the robots as quickly as possible? The initial locations of the robots are unknown to each other, therefore the problem must be solved in an online fashion. For this problem, we present an algorithm whose competitive ratio is $O(H \cdot\max\{M,\ \sqrt{MH}\})$ for arbitrary robot deployments, where M is the largest edge length in the Euclidean minimum spanning tree on the initial robot configuration and H is the height of the tree. We also study the case when the robot initial positions are chosen uniformly at random and improve the ratio to $O(M)$. Finally, we present simulation results to validate the performance in larger scales and demonstrate our algorithm using three robots in a field experiment.

We study the problem of computing shortest collision-free Dubins paths when turning a corner. We present a sufficient condition for a closed-form solution. Specifically, consider S as the set consisting of paths of the form RSRSR, RSRSL, LSRSR and LSRSL that pass through the interior corner, where sub-paths RSR, RSL, and LSR are elementary Dubins paths composed of segments which are either straight (S) or turning left (L) or right (R). We find the closed-form optimal path around a corner when S is nonempty. Our solution can be used in an efficient path planner, for example, when navigating corridors. It can also be used as a subroutine for planners such as RRTs.

With the proliferation of small aerial vehicles, acquiring close up imagery for high quality reconstruction is gaining importance. We present an adaptive view planning method to collect such images in an automated fashion. We first start by sampling a small set of views to build a coarse proxy to the scene. We then present (i) a method that builds a set of adaptive viewing planes for efficient view selection and (ii) an algorithm to plan a trajectory that guarantees high reconstruction quality which does not deviate too much from the optimal one. The vehicle then follows the trajectory to cover the scene, and the procedure is repeated until reconstruction quality converges or a desired level of quality is achieved. The set of viewing planes provides an effective compromise between using the entire 3D free space and using a single view hemisphere to select the views. We compare our algorithm to existing methods in three challenging scenes. Our algorithm generates views which produce the least reconstruction error comparing to three different baseline approaches.

We consider the problem of minimizing the time to approach and land near a target radio beacon at an unknown location with an Unmanned Aerial Vehicle (UAV). We show that a cone-like region exists above the target inside of which bearing measurements of a directional antenna lose directionality: signal recordings in all directions yield similar signal strength. We present a geometric model of this region based on antenna simulations and data collected with a real system. Our main contribution is a strategy that takes advantage of a UAV's ability to change altitude and exploits a special structure occurring when approaching the target beacon from above to reduce the flight time required to land near the beacon. We analyze the performance of our strategy and demonstrate through simulations that by exploiting this structure we can achieve shorter flight times than our previous work.

We present a novel method enabling robots to quickly learn to manipulate objects by leveraging a motion planner to generate “expert” training trajectories from a small amount of human-labeled data. In contrast to the traditional sense-plan-act cycle, we propose a deep learning architecture and training regimen called PtPNet that can estimate effective end-effector trajectories for manipulation directly from a single RGB-D image of an object. Additionally, we present a data collection and augmentation pipeline that enables the automatic generation of large numbers (millions) of training image and trajectory examples with almost no human labeling effort.We demonstrate our approach in a non-prehensile tool-based manipulation task, specifically picking up shoes with a hook. In hardware experiments, PtPNet generates motion plans (open-loop trajectories) that reliably (89% success over 189 trials) pick up four very different shoes from a range of positions and orientations, and reliably picks up a shoe it has never seen before. Compared with a traditional sense-plan-act paradigm, our system has the advantages of operating on sparse information (single RGB-D frame), producing high-quality trajectories much faster than the expert planner (300ms versus several seconds), and generalizing effectively to previously unseen shoes. Video available at https://youtu.be/voIkyiBtwn4.

We study a fundamental motion planning problem of navigating a ground robot to a goal position with minimum energy consumption. Most existing solutions for this problem require an energy consumption model as a function of the environment and the robot motion. Obtaining such models is difficult which prevents the practical applicability of path planning algorithms for energy optimization. To address this issue, we present a new approach based on the assumption that the energy consumption for the ground robot is correlated with ground appearance. The first main contribution of this paper is the validation of the ground appearance assumption by experiments using actual energy consumption data obtained by ground robots. We then show how aerial images collected by an unmanned aerial vehicle can be used to generate the energy cost map of a given environment, which can further be used for planning energy-efficient paths for ground robots.

This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle α and height H when their apex points lie on a planar surface. This is a novel variant of the 3D Traveling Salesman Problem with intersecting Neighborhoods (TSPN) called Cone-TSPN. When the cones are allowed to tilt by an angle c we have the tilted Cone-TSPN problem, to which we present an algorithm that returns a solution with an approximation ratio of O (1+tan α/1-tan ϵ tan α (1 + log max(H)/min(H)). We demonstrate through simulations that our algorithm can be implemented in a practical way and by exploiting the structure of the cones we can achieve shorter tours. Finally, we present results from covering a reflective surface (lake area) that shows the importance of selecting different view angles under strong sunlight specularities.

In the coverage path planning problem, a common assumption is that the robot can fully cover the environment without recharging. However, in reality most mobile robot systems operate under battery limitations. To incorporate this constraint, we consider the problem when the working environment is large and the robot needs to recharge multiple times to fully cover the environment. We focus on a geometric version where the environment is represented as a polygonal grid with a single charging station. Energy consumption throughout the environment is assumed to be uniform and proportional to the distance traveled. We first present a constant-factor approximation algorithm for contour-connected environments. We then extend the algorithm for general environments. We also validate the results in experiments performed with an aerial robot.

This paper presents a novel cable-driven gripper with perception capabilities for autonomous harvesting of strawberries. Experiments show that the gripper allows for more accurate and faster picking of strawberries compared to existing systems. The gripper consists of four functional parts for sensing, picking, transmission, and storing. It has six fingers that open to form a closed space to swallow a target strawberry and push other surrounding berries away from the target. Equipped with three IR sensors, the gripper controls a manipulator arm to correct for positional error, and can thus pick strawberries that are not exactly localized by the vision algorithm, improving the robustness. Experiments show that the gripper is gentle on the berries as it merely cuts the stem and there is no physical interaction with the berries during the cutting process. We show that the gripper has close-to-perfect successful picking rate when addressing isolated strawberries. By including internal perception, we get high positional error tolerance, and avoid using slow, high-level closed-loop control. Moreover, the gripper can store several berries, which reduces the overall travel distance for the manipulator, and decreases the time needed to pick a single strawberry substantially. The experiments show that the gripper design decreased picking execution time noticeably compared to results found in literature.

This paper considers the problem of choosing measurement locations of an aerial robot in an online manner in order to localize an animal with a radio collar. The aerial robot has a commercial, low-cost directional antenna and USB receiver to capture the signal. It uses its own movement to obtain a bearing measurement. The uncertainty in these measurements is assumed to be bounded and represented as wedges. The measurements are then merged by intersecting the wedges. The localization uncertainty is quantified by the area of the resulting intersection. The goal is to reduce the localization uncertainty to a value below a given threshold in minimum time. We present an online strategy to choose measurement locations during execution based on previous readings and analyze its performance with competitive analysis. The time required to localize a target is upper-bounded by the function of measurement noise, desired localization uncertainty and minimum step length. We also validate the strategy in extensive simulations and show its applicability through field experiments over a 5 hectare area using an autonomous aerial robot equipped with a directional antenna.

Estimating accurate and reliable fruit and vegetable counts from images in real-world settings, such as orchards, is a challenging problem that has received significant recent attention. Estimating fruit counts before harvest provides useful information for logistics planning. While considerable progress has been made toward fruit detection, estimating the actual counts remains challenging. In practice, fruits are often clustered together. Therefore, methods that only detect fruits fail to offer general solutions to estimate accurate fruit counts. Furthermore, in horticultural studies, rather than a single yield estimate, finer information such as the distribution of the number of apples per cluster is desirable. In this work, we formulate fruit counting from images as a multi-class classification problem and solve it by training a Convolutional Neural Network. We first evaluate the per-image accuracy of our method and compare it with a state of the art method based on Gaussian Mixture Models over four test datasets. Even though the parameters of the Gaussian Mixture Model based method are specifically tuned for each dataset, our network outperforms it in three out of four datasets with a maximum of 94% accuracy. Next, we use the method to estimate the yield for two datasets for which we have ground truth. Our method achieved 96-97% accuracies. For additional details please see our video here: https://www.youtube.com/watch?v=Le0mb5P-SYc.

We consider the problem of building accurate three dimensional (3D)reconstructions of orchard rows. This problem arises in many applications including yield mapping and measuring traits (e.g. trunk diameters)for phenotyping. While 3D reconstructions of side views can be obtained using standard methods, merging the two side-views is difficult due to the lack of overlap between the two partial reconstructions. We present a novel method that utilizes global features to constrain the solution. Specifically, we use information from the silhouettes and the ground plane for alignment. The method is evaluated using multiple simulated and real datasets. For additional information and demonstration of experimental results please see https://www.youtube.com/watch?v=6mGMF2gFv4M.

We present a novel method for extrinsically calibrating a camera and a 2-D Laser Rangefinder (LRF) whose beams are invisible from the camera image. We show that point-to-plane constraints from a single observation of a V-shaped calibration pattern composed of two non-coplanar triangles suffice to uniquely constrain the relative pose between two sensors. Next, we present an approach to obtain solutions using point-to-plane constraints from single or multiple observations. Along the way, we also show that previous solutions, in contrast to our method, have inherent ambiguities and therefore must rely on a good initial estimate. Real and synthetic experiments validate our method and show that it achieves better accuracy than previous methods.

Most Unmanned Aerial Vehicle (UAV) controllers require linear velocities as input. An effective method to obtain linear velocity is to place a downward facing camera and to estimate the velocity from the optical flow. However, this technique fails in outdoor environments when the ground is covered with grass or other objects which move due to winds such as those caused by the propellers. We present a novel method to estimate the linear velocities from stereo images even in the presence of disorderly motion of image features. We validate the approach using imagery obtained from a UAV flying through orchard rows.

We consider an agricultural automation scenario where a robot, equipped with a camera mounted on a manipulator, is charged with counting the number of apples in an orchard. We focus on the subtask of planning views so as to accurately estimate the number of apples in an apple cluster. We present a method to efficiently enumerate combinatorially distinct world models and to compute the most likely model from one or more views. These are incorporated into single and multi-step planners. We evaluate these planners in simulation as well as with experiments on a real robot.

We present algorithms for environment exploration in the context of a habitat monitoring task, where the goal is to track radio-tagged invasive fish with autonomous surface or ground robots. The first task is navigation around an unknown obstacle using an input from a front-facing sonar. This capability is important for navigation on inland lakes, because plants and shallow shorelines are hard to map in advance. The second task involves energy harvesting for long-term operation. We address the problem of exploring the solar map of the environment which is used for energy-efficient navigation. For both problems, we present online algorithms and examine their performance using competitive analysis. In competitive analysis, the performance of an online algorithm is compared against the optimal offline algorithm. For obstacle avoidance, the offline algorithm knows the shape of the obstacle. For solar exploration, the offline algorithm knows the geometry of the shadow-casting objects. We obtain an $O(1)$ competitive ratio for obstacle avoidance and an $O(\log n)$ competitive ratio for solar exploration, where $n$ is the number of critical points to observe. The strategies for obstacle avoidance are validated through extensive field experiments, and the strategies for exploration are validated with simulations.

We present a general framework for accurate positioning of sensors and end effectors in farm settings using a camera mounted on a robotic manipulator. Our main contribution is a visual servoing approach based on a new and robust feature tracking algorithm. Results from field experiments performed at an apple orchard demonstrate that our approach converges to a given termination criterion even under environmental influences such as strong winds, varying illumination conditions and partial occlusion of the target object. Further, we show experimentally that the system converges to the desired view for a wide range of initial conditions. This approach opens possibilities for new applications such as automated fruit inspection, fruit picking or precise pesticide application.

The papers included in this special section were presented at the 11th Workshop on the Algorithmic Foundations of Robotics (WAFR), which was held at Boğaziçi University, Istanbul, Turkey, during August 3–5, 2014.

This paper addresses a fundamental search problem in which a searcher subject to time and energy constraints tries to find a mobile target. The target's motion is modeled as a random walk on a discrete set of points on a line segment. At each time step, the target chooses one of the adjacent nodes at random and moves there. We study two detection models. In the no-crossing model, the searcher detects the target if it is on the same node or if it takes the same edge at the same time. In the crossing model, detection happens only if the target lands on the same node at the same time. For the no-crossing model, where move and stay actions may have different costs, we present an optimal search strategy under energy and time constraints. For the crossing model, we formulate the problem of designing an optimal strategy as a partially observable Markov decision process (POMDP) and solve it using methods that reduce the state-space representation of the belief. The POMDP solution reveals structural properties of the optimal solution. We use this structure to design an efficient strategy and analytically study its performance. Finally, we present preliminary experimental results to demonstrate the applicability of our model to our tracking system, which is used for finding radio-tagged invasive fish.

Energy harvesting using solar panels can significantly increase the operational life of mobile robots. If a map of expected solar power is available, energy efficient paths can be computed. However, estimating this map is a challenging task, especially in complex environments. In this paper, we show how the problem of estimating solar power can be decomposed into the steps of magnitude estimation and solar classification. Then, we provide two methods to classify a position as sunny or shaded: a simple data-driven Gaussian Process method and a method that estimates the geometry of the environment as a latent variable. Both of these methods are practical when the training measurements are sparse, such as with a simple robot that can only measure solar power at its own position. We demonstrate our methods on simulated randomly generated environments. We also justify our methods with measured solar data by comparing the constructed height maps with satellite images of the test environments, and in a cross-validation step where we examine the accuracy of predicted shadows and solar current.

We study two new informative path planning problems that are motivated by the use of aerial and ground robots in precision agriculture. The first problem, termed sampling traveling salesperson problem with neighborhoods (SAMPLINGTSPN), is motivated by scenarios in which unmanned ground vehicles (UGVs) are used to obtain time-consuming soil measurements. The input in SAMPLINGTSPN is a set of possibly overlapping disks. The objective is to choose a sampling location in each disk and a tour to visit the set of sampling locations so as to minimize the sum of the travel and measurement times. The second problem concerns obtaining the maximum number of aerial measurements using an unmanned aerial vehicle (UAV) with limited energy. We study the scenario in which the two types of robots form a symbiotic system-the UAV lands on the UGV, and the UGV transports the UAV between deployment locations. This paper makes the following contributions. First, we present an O((rmax)/(rmin)) approximation algorithm for SAMPLINGTSPN, where rminand rmaxare the minimum and maximum radii of input disks. Second, we show how to model the UAV planning problem using a metric graph and formulate an orienteering instance to which a known approximation algorithm can be applied. Third, we apply the two algorithms to the problem of obtaining ground and aerial measurements in order to accurately estimate a nitrogen map of a plot. Along with theoretical results, we present results from simulations conducted using real soil data and preliminary field experiments with the UAV.

The papers in this special section were presented at the 11th Workshop on the Algorithmic Foundation of Robotics (WAFR), which was held at Boğaziçi University, Istanbul, Turkey, during August 3–5, 2014. WAFR is a prestigious biennial single-track workshop on algorithms for robotics and automation. It features cutting-edge research in a broad range of planning problems (such as manipulation, motion, path, multi-robot, and kynodynamic planning), geometric and topological computation, and novel applications like surgical planning, active sensing, and informative path planning.

We study the problem of actively locating a static target using mobile robots equipped with bearing sensors. The goal is to reduce the uncertainty in the target's location to a value below a given threshold in minimum time. Our cost formulation explicitly models time spent in traveling, as well as taking measurements. In addition, we consider distance-based communication constraints between the robots. We provide the following theoretical results. First, we study the properties of an optimal offline strategy for one or more robots with access to the target's true location. We derive the optimal offline algorithm and bound its cost when considering a single robot or an even number of robots. In other cases, we provide a close approximation. Second, we provide a general method of converting the offline algorithm into an online adaptive algorithm (that does not have access to the target's true location), while preserving near optimality. Using these two results, we present an online strategy proven to locate the target up to a desired uncertainty level at near-optimal cost. In addition to theoretical analysis, we validate the algorithm in simulations and multiple field experiments performed using autonomous surface vehicles carrying radio antennas to localize radio tags.

In this paper, we study the problem of quickly building the 3D model of an outdoor environment from measurements obtained by a robot equipped with a solar panel. The robot knows the angle of the sun and the locations of the objects in the environment. It does not know, however, the height of the objects. For example, it might be possible to use satellite images to obtain locations of trees in a field but not their heights. In order to compute the height of an object, the robot must find the projection of the object's highest point. This is where the shadow of the object ends. The robot can find it by tracing the shadow (moving parallel to the sun) until the measurement switches from shadow to sun or vice versa. The robot's goal is to compute the height of every object as quickly as possible using only solar measurements. We formulate this as an online optimization problem. The optimal offline algorithm is given by the Traveling Salesman path of the transition points. The robot does not know these locations a priori. It must search for each of them. We present an algorithm with the property that for n objects, our distance traveled is guaranteed to be within a factor O(log n) of this optimal offline tour. In addition to analytical proofs, we demonstrate the algorithm with simulations using solar data collected from field experiments, and examine its performance for uniformly distributed sites.

The art gallery problem is a classical sensor placement problem that asks for the minimum number of guards required to see every point in an environment. The standard formulation does not take into account self-occlusions caused by a person or an object within the environment. Obtaining good views of an object from all orientations is important for surveillance and visual tracking applications. We study the art gallery problem under a constraint, termed Δ-guarding, that ensures that all sides of any convex object are always visible in spite of self-occlusion. Our contributions in this paper are two-fold: we first prove that Ω(√n) guards are always necessary for Δ-guarding the interior of a simple polygon having n vertices. Next, we study the problem of Δ-guarding a set of line segments connecting points on the boundary of the polygon. This is motivated by applications where an object or person of interest can only move along certain paths in the polygon. We present a constant factor approximation algorithm for this problem - one of the few such results for art gallery problems.

We study the lion-and-man game in which a group of lions (the pursuers) try to capture a man (the evader). The players have equal speed. They can observe each other at all times. While the game is well-studied in planar domains such as polygons, very little is known about its properties in higher dimensions. In this paper, we study the lion and man game when played on the surface of a genus-zero polyhedron with boundary. We show that three lions with non-zero capture distance δ can capture the man in time O((A/δ2+ L/δ)2δ/2) where A is the area of the surface, and L is the total edge length of the surface.

This paper studies the problem of searching for an unknown moving target in a bounded two-dimensional convex area with a mobile robot. A key component of designing a search strategy is the target motion model, which is often unknown in practical scenarios. When designing search strategies, researchers either (1) ignore the target motion and treat the target as a stationary object with unknown location, (2) treat the target as an adversary and model the search task as a game, or (3) use a stochastic model such as a random walk. For each of these models we analyze possible search paths with the objective of minimizing the expected capture time. Our intent is to investigate how the choice of the model influences the choice of the strategy and consequently how the capture time will depend on this choice. In addition to a theoretical analysis, we compare the strategies in simulation.

We study the problem of tracking mobile targets using a team of aerial robots. Each robot carries a camera to detect targets moving on the ground. The overall goal is to plan for the trajectories of the robots in order to track the most number of targets, and accurately estimate the target locations using the images. The two objectives can conflict since a robot may fly to a higher altitude and potentially cover a larger number of targets at the expense of accuracy. We start by showing that k ≥ 3 robots may not be able to track all n targets while maintaining a constant factor approximation of the optimal quality of tracking at all times. Next, we study the problem of choosing robot trajectories to maximize either the number of targets tracked or the quality of tracking. We formulate this problem as the weighted version of a combinatorial optimization problem known as the Maximum Group Coverage (MGC) problem. A greedy algorithm yields a 1/2 approximation for the weighted MGC problem. Finally, we evaluate the algorithm and the sensing model through simulations and preliminary experiments.

We study the problem of placing bearing sensors so as to estimate the location of a target in a square environment. We consider sensors with unknown but bounded noise: the true location of the target is guaranteed to be in a 2α-wedge around the measurement, where α is the maximum noise. The quality of the placement is given by the area or diameter of the intersection of measurements from all sensors in the worst-case (i.e. regardless of the target's location). We study the bi-criteria optimization problem of placing a small number of sensors while guaranteeing a worst-case bound on the uncertainty. Our main result is a constant-factor approximation: We show that in general when α ≤ Π/4, at most 9n* sensors placed on a triangular grid has diameter and area uncertainty of at most 5.88UD* and 7.76UA* respectively, where n*,UD* and UA* are the number of sensors, diameter and area uncertainty of an optimal algorithm. In obtaining these results, we present some structural properties which may be of independent interest. We also show that in the triangular grid placement, only a constant number of sensors need to be activated to achieve the desired uncertainty, a property that can be used for designing energy/bandwidth efficient sensor selection schemes.

We present deterministic strategies for capturing a target performing a discrete random walk on a discretized line segment. The searcher has a limited time budget. Its goal is to maximize the probability of capturing the target within the budget. A challenging aspect of our model is that the target can cross the searcher without being captured when they take the same edge at the same time in opposite directions. We present a Partially Observable Markov Decision Process (POMDP) approach for finding the optimal search strategy. We also present an efficient approximate solution to the POMDP. The strategies found by this approach reveal structural properties of the efficient search strategies which we exploit to solve the problem efficiently without running the POMDP.

In this paper we study the problem of designing search strategies to find a target whose motion is described by a random walk along a one-dimensional bounded environment. The sensing model and the characteristic of the environment require the searcher and the target to be on the same site at the same time to guarantee capture. The objective is to optimize the searcher's motion, given by a sequence of actions (move right, left or remain stationary), so that the probability of capturing the target is maximized. Each action is associated with an energy cost. The searcher strategy is constrained by a total energy budget. We propose a class of randomized strategies for which we provide an analytical expression for the capture probability as a function of a single parameter. We then use this expression to find the best strategy within this class. In addition to theoretical results, the algorithms are analyzed in simulation and compared with other intuitive solutions.

We study the problem of coordinating an Unmanned Aerial Vehicle (UAV) and an Unmanned Ground Vehicle (UGV) for a precision agriculture application. In this application, the ground and aerial measurements are used for estimating nitrogen (N) levels on-demand across a farm. Our goal is to estimate the N map over a field and classify each point based on N deficiency levels. These estimates in turn guide fertilizer application. Applying the right amount of fertilizer at the right time can drastically reduce fertilizer usage. Towards building such a system, this paper makes the following contributions: First, we present a method to identify points whose probability of being misclassified is above a threshold. Second, we study the problem of maximizing the number of such points visited by an UAV subject to its energy budget. The novelty of our formulation is the capability of the UGV to mule the UAV to deployment points. This allows the system to conserve the short battery life of a typical UAV. Third, we introduce a new path planning problem in which the UGV must take a measurement within a disk centered at each point visited by the UAV. The goal is to minimize the total time spent in traveling and measuring. For both problems, we present constant-factor approximation algorithms. Finally, we demonstrate the utility of our system with simulations which use manually collected soil measurements from the field.

In the rendezvous search problem, two robots at unknown locations must successfully meet somewhere in the environment. We study the symmetric version of the problem in which they must use the same strategy. We provide a new algorithm for the symmetric rendezvous problem on the line. Our symmetric strategy has a competitive ratio of 17.686 for total distance traveled and a competitive ratio of 24.843 for total time. Both are improvements over the previously best-known algorithm, which has (time and distance) a competitive ratio of 26.650. Our algorithm can be adapted for bounded linear environments and simple closed curves with the same performance guarantees. It is also robust with respect to errors in motion and differences in robots' starting times. We confirm our theoretical results through simulations and show that our algorithms are practical by reporting the results of real robot deployments in indoor environments.

We study the symmetric rendezvous search problem in which two robots that are unaware of each other’s locations try to meet as quickly as possible. In the symmetric version of this problem, the robots are required to execute the same strategy. First, we present a symmetric rendezvous strategy for the robots that are initially placed on the open plane and analyze its competitive performance. We show that the competitive complexity of our strategy is O(d/R) where d is the initial distance between the robots and R is the communication radius. Second, we extend the symmetric rendezvous strategy for the open plane to unknown environments with polygonal obstacles. The extended strategy guarantees a complete coverage of the environment. We analyze the strategy for square, translating robots and show that the competitive ratio of the extended strategy is O(d/D) where D is the length of the sides of the robots. In obtaining this result, we also obtain an upper bound on covering arbitrary polygonal environments which may be of independent interest.

We study the problem of minimizing the time to accurately localize a target using radio-based telemetry. The directional nature of the antenna allows us to obtain bearing-to-target sensor measurements. There are two critical attributes that separate our setup from the majority of bearing-only tracking literature: sensing ambiguity and long measurement time. We provide a sensing strategy which mitigates the effect of ambiguity, and prove that the time required to localize a target is less than a constant times that of any bearing-based localization strategy which uses an Extended Kalman Filter.

Modeling human motion in complex environments without losing long-range dependencies is difficult due to the large number of combinatorially distinct paths humans may follow. Existing representations avoid this difficulty by limiting the prediction of human motion to a local level. As a result, robot motion planning algorithms that use these representations are reactive in nature, and fail to exploit higher-order dependencies. We present a novel motion model capable of representing the global path behavior of people. Our model compactly encodes higher-order temporal dependencies inherent in human mobility traces on an abstract representation of the environment that lends itself to combinatorial planning. We incorporate uncertainties into the planning process using POMDPs and present a general predictive multi-robot planning algorithm applicable to pedestrian datasets commonly found in the literature. We evaluate our planner by simulating multiple instances of a variant of the visibility-based target-tracking problem inspired by our previous work. We report encouraging results that demonstrate our multi-robot plans exhibit desirable combinatorial structure, e.g. robot re-use.

Mobile robots can be used as mobile hubs to provide communication services on-demand. This capability is especially valuable in disaster response scenarios where there is no communication infrastructure. In such scenarios, mobile hubs can provide a communication infrastructure in a dynamic fashion. In this paper, we study the problem of building a communication bridge between a source s and a destination t with mobile robots. Given a set of robots P and their initial locations, our goal is to find a subset S of robots and their final locations such that the robots in S create a communication bridge between s and t in their final locations. We introduce a new optimization problem for building communication bridges. The objective is to minimize the number of hubs (i.e., |S|), while simultaneously minimizing the robots' motion. The two mobility measures studied in this paper are: (i) maximum travel distance and (ii) total travel distance of the robots. For a geometric version of the problem where the robots must move onto the line segment [s, t], we present polynomial time algorithms which use the minimum number of hubs while remaining within a constant factor of a given motion measure.

We consider the problem of deploying robots in formations that ensure network connectivity between a fixed base station and a set of independent agents wandering in the environment. We adopt a communications model that requires line-of-sight and then solve for robot placements by finding mutually-visible configurations in a polygonal decomposition of the environment map. Both the static deployment case and the case of finding deployments that minimize total robot movement are considered. We provide algorithms for the moving agent case, consider their performance on various discretizations for a range of problem sizes, and discuss our experimental implementation of the presented ideas.

For battery-powered mobile robots to operate for long periods of time, it is critical to optimize their motion so as to minimize energy consumption. The driving motors are a major source of power consumption. In this paper, we study the problem of finding velocity profiles for car-like robots so as to minimize the energy consumed while traveling along a given path. We start with an established model for energy consumption of DC motors. We present closed form solutions for the unconstrained case and for the case where there is a bound on maximum velocity. We also study a general problem where the robot's path is composed of segments (e.g. circular arcs and line segments). We are given a velocity bound for each segment. For this problem, we present a dynamic programming solution which uses the solution for the single-constraint case as a subroutine. In addition, we present a calibration method to find model parameters. Finally, we present results from experiments conducted on a custom-built robot.

We present a novel robotic telemetry system for localizing radio-tagged invasive fish in frozen lakes using coarse bearing measurements. We address the problem of selecting sensing locations so as to minimize the uncertainty in the location of the target. For this purpose, we propose three active localization algorithms and evaluate them both in simulations and through field experiments. We also present a novel technique for bearing-estimation from directional radio antenna which is critical for the successful execution of the active localization algorithms. Our system is able to operate on frozen lakes and localize the target to within values as low as one meter.

Robotic Sensor Networks (RSNs) find increasing use in environmental monitoring as RSNs can collect data from obscure, hard-to-reach places over long periods of time. This work reports progress in building a network of small, light-weight robotic rafts which will be used to monitor common carp tagged with radio transmitters across Minnesota lakes. We describe the design and architecture of the robotic raft, and demonstrate the robustness of our waypoint navigation algorithm through field tests conducted in various lakes. We also present results from experiments aimed towards localizing tagged fish.

Telepresence or tele-immersion technologies allow people to attend a shared meeting without being physically present in the same location. Commercial telepresence solutions available in the market today have significant drawbacks - they are very expensive, and confine people to the area covered by stationary cameras. In this paper, we present a mobile tele-immersion platform that addresses these issues by using robots with embedded cameras. In our system, the users can move around freely because robots autonomously adjust their locations. We provide a geometric definition of what it means to get a good view of the user, and present control algorithms to maintain a good view. The algorithms are validated both in simulation and in real experiments.

Allowing robots to communicate naturally with humans is an important goal for social robotics. Most approaches have focused on building high-level probabilistic cognitive models. However, research in cognitive science shows that people often build common ground for communication with each other by seeking and providing evidence of understanding through behaviors like mimicry. Predictive State Representations (PSRs) allow one to build explicit, low-level models of the expected outcomes of actions, and are therefore well-suited for tasks that require providing such evidence of understanding. Using human-robot shadow puppetry as a prototype interaction study, we show that PSRs can be used successfully to both model human interactions, and to allow a robot to learn on-line how to engage a human in an interesting interaction.

Robotic routers (mobile robots with wireless communication capabilities) can create an adaptive wireless network and provide communication services for mobile users on-demand. Robotic routers are especially appealing for applications in which there is a single mobile user whose connectivity to a base station must be maintained in an environment that is large compared to the wireless range. In this paper, we study the problem of computing motion strategies for robotic routers in such scenarios, as well as the minimum number of robotic routers necessary to enact our motion strategies. Assuming that the routers are as fast as the user, we present an optimal solution for cases where the environment is a simply-connected polygon, a constant factor approximation for cases where the environment has a single obstacle, and an O(h) approximation for cases where the environment has h circular obstacles. The O(h) approximation also holds for cases where the environment has h arbitrary polygonal obstacles, provided they satisfy certain geometric constraints - e.g. when the set of their minimum bounding circles is disjoint.

Robots operating in a workspace can localize themselves by querying nodes of a sensor-network deployed in the same workspace. This paper addresses the problem of computing the minimum number and placement of sensors so that the localization uncertainty at every point in the workspace is less than a given threshold. We focus on triangulation-based state estimation, where measurements from two sensors must be combined for an estimate. This problem is NP-hard in its most general from. For the general version, we present a solution framework based on integer linear programming and demonstrate its application in a fire-tower placement task. Next, we study the special case of bearing-only localization and present an approximation algorithm with a constant factor performance guarantee.

Humans rely on a finely tuned ability to recognize and adapt to socially relevant patterns in their everyday face-to-face interactions. This allows them to anticipate the actions of others, coordinate their behaviors, and create shared meaning to communicate. Social robots must likewise be able to recognize and perform relevant social patterns, including interactional synchrony, imitation, and particular sequences of behaviors. We use existing empirical work in the social sciences and observations of human interaction to develop nonverbal interactive capabilities for a robot in the context of shadow puppet play, where people interact through shadows of hands cast against a wall. We show how information theoretic quantities can be used to model interaction between humans and to generate interactive controllers for a robot. Finally, we evaluate the resulting model in an embodied human-robot interaction study. We show the benefit of modeling interaction as a joint process rather than modeling individual agents.

We study a path planning problem which arises when multiple robots are used to gather data from stationary devices with wireless communication capabilities. Each device has a given communication range, and stores a fixed amount of data. The objective of the robots is to gather the data from these devices and to upload it to a base-station/gateway. We introduce a new optimization problem called the Data Gathering Problem (DGP). In DGP, the objective is to compute a tour for each robot in such a way that minimizes the time to collect data from all devices. In order to download the data from a device, a robot must visit a point within the communication range of the device. Then, it spends a fixed amount of time to download the data. Thus, the time to complete a tour depends on not only the travel time but also the time to download the data, and the number of devices visited along the tour. First, we study a special case of DGP where the robots' motion is restricted to a curve which contains the base station at one end. Next, we study the 2D version. We show that two existing algorithms for variants of the Traveling Salesperson Problem can be combined and adapted to obtain a constant factor approximation to DGP. Afterwards, we present an improvement for sparse deployments. We also present simulations which shed light on the utility of data gathering using mobile robots.

In the lion and man game, a lion tries to capture a man who is as fast as the lion. We study a new version of this game which takes place in a Euclidean environment with a circular obstacle. We present a complete characterization of the game: for each player, we derive necessary and sufficient conditions for winning the game. Their (continuous time) strategies are constructed using techniques from differential games and arguments from geometry. Our main result is a decision algorithm which takes arbitrary initial positions as input, declares one of the players as the winner of the game and outputs a winning strategy for that player. We extend our approach to explicitly construct, in closed form, the decision boundary that partitions the arena into win and lose regions.

We study a variant of a well-known pursuit evasion game, the lion and man game. In this game a lion (the pursuer) tries to capture a man (the evader). The players move in turns. At each time step, they can move a unit distance. We focus on a version which takes place in an unbounded arena: the positive quadrant of the plane. The novelty of our formulation is in the sensor model. In the original formulation, the lion can sense the precise location of the man at all times. In our version, which is inspired by mobile robots equipped with monocular vision systems, the lion can only obtain bearing information about the man's location. We present a pursuit strategy which guarantees that the distance between the players is reduced to the step size in a bounded number of steps.

Mobile robots equipped with wireless networking capabilities can act as robotic routers and provide network connectivity to mobile users. Robotic routers provide cost efficient solutions for deployment of a wireless network in a large environment with limited number of users. In this paper, we present motion planning algorithms for robotic routers to maintain the connectivity of a single user to a base station. We consider two motion models for the user. In the first model, we assume that the target's motion is known in advance. In the second model, user moves in an adversarial fashion and tries to break the connectivity.

We address the sensor selection problem which arises in tracking and localization applications. In sensor selection, the goal is to select a small number of sensors whose measurements provide a good estimate of a target's state (such as location). We focus on the bounded uncertainty sensing model where the target is a point in thed-dimensional Euclidean space. Each sensor measurement corresponds to a convex polyhedral subset of the space. The measurements are merged by intersecting corresponding sets. We show that, on the plane, four sensors are sufficient (and sometimes necessary) to obtain an estimate whose area is at most twice the area of the best possible estimate (obtained by intersecting all measurements). We also extend this result to arbitrary dimensions and show that a constant number of sensors suffice for a constant factor approximation in arbitrary dimensions. Both constants depend on the dimensionality of the space but are independent of the total number of sensors in the network.

We study the problem of designing motion-planning and sensor assignment strategies for tracking multiple targets with a mobile sensor network. We focus on triangulation based tracking where two sensors merge their measurements in order to estimate the position of a target. We present an iterative and distributed algorithm for the tracking problem. An iteration starts with an initialization phase where targets are assigned to sensor pairs. Afterwards, assigned sensors relocate to improve their estimates. We refer to the problem of computing new locations for sensors (for given target assignments) as one-step tracking. After observing that one-step tracking is computationally hard, we show how it can be formulated as an energy-minimization problem. This allows us to adapt well-studied distributed algorithms for energy minimization. We present simulations to compare the performance of two such algorithms and conclude the paper with a description of the full tracking strategy. The utility of the presented strategy is demonstrated with simulations and experiments on a sensor network platform

Robots operating in a workspace can localize themselves by querying nodes of a sensor-network deployed in the same workspace. This paper addresses the problem of computing the minimum number and placement of sensors so that the localization uncertainty at every point in the workspace is less than a given threshold. We focus on triangulation based state estimation where measurements from two sensors must be combined for an estimate. We show that the general problem for arbitrary uncertainty models is computationally hard. For the general problem, we present a solution framework based on integer linear programming and demonstrate its practical feasibility with simulations. Finally, we present an approximation algorithm for a geometric uncertainty measure which simultaneously addresses occlusions, angle and distance constraints.

Mobile sensors cover more area over a fixed period of time than do the same number of stationary sensors. However, the quality of coverage (QoC) achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed, and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper, we consider the following event capture problem: the events of interest arrive at certain points in the sensor field and disappear according to known arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. We analyze how the QoC scales with velocity, path, and number of mobile sensors. We characterize cases where the deployment of mobile sensors has no advantage over static sensors, and find the optimal velocity pattern that a mobile sensor should adopt. We also present algorithms for two motion planning problems: 1) for a single sensor, what is the sensor trajectory and theminimum speedrequired to satisfy a bound on the event loss probability and 2) for sensors with fixed speed, what is theminimum number of sensorsrequired to satisfy a bound on the event loss probability. When the robots are restricted to move along a line or a closed curve, our algorithms return the optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor of 2 of the optimal solution. For the case where the events occur at arbitrary points on a plane, we present heuristic algorithms for the aforementioned motion planning problems and bound their performance with respect to the optimal.

We address the problem of placing a sensor network so as to minimize the uncertainty in estimating the position of targets. The novelty of our formulation is in the sensing model: we focus on stereo sensors where the measurements from two sensors must be combined for an estimation. We study two versions of this problem. In the first version, which we call the placement problem, we are given a workspace and an error threshold. The objective is to place a minimum number of cameras so that no matter where the target is located in the workspace, the uncertainty in localizing it is less than the threshold. For this problem, we present an approximation algorithm and prove that the deviation of its performance from the optimal value is bounded by a constant. In the second version, called the deployment problem, we study the problem of relocating a mobile sensor team to minimize the uncertainty in localizing possibly moving targets. We present a distributed, discrete-time algorithm which explicit addresses communication and motion constraints and show how to compute the optimal move within the time-step for a given target/sensor-pair assignment. The utility of the algorithm is demonstrated with simulations

Mobile sensors cover more area over a period of time than the same number of stationary sensors. However, the quality of coverage achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper we consider the problem of event capture using mobile sensors. The events of interest arrive at certain points in the sensor field and fade away according to arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. For this scenario we analyze how the quality of coverage scales with the velocity, path and number of mobile sensors. We characterize the cases where the deployment of mobile sensors has no advantage over static sensors and find the optimal velocity pattern that a mobile sensor should adopt.We also present algorithms for two motion planning problems: (i) for a single sensor, what is the minimum speed and sensor trajectory required to satisfy a bound on event loss probability and (ii) for sensors with fixed speed, what is the minimum number of sensors required to satisfy a bound on event loss probability. When events occur only along a line or a closed curve our algorithms return optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor two of the optimal solution. For the case where the events occur at arbitrary points on a plane we present heuristic algorithms for the above motion planning problems and bound their performance with respect to the optimal. The results of this paper have wide range of applications in areas like surveillance, wildlife monitoring, hybrid sensor networks and under-water sensor networks.

We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the hunters but it can see them only if they are located on adjacent nodes. We show that two hunters suffice for catching rabbits with such local visibility with high probability. We distinguish between reactive rabbits who move only when a hunter is visible and general rabbits who can employ more sophisticated strategies. We present polynomial time algorithms that decide whether a graph G is hunter-win, that is, if a single hunter can capture a rabbit of either kind on G.

We address the problem of selecting sensors so as to minimize the error in estimating the position of a target. We consider a generic sensor model where the measurements can be interpreted as polygonal, convex subsets of the plane. In our model, the measurements are merged by intersecting corresponding subsets, and the measurement uncertainty corresponds to the area of the intersection. This model applies to a large class of sensors, including cameras. We present an approximation algorithm which guarantees that the resulting error in estimation is within factor 2 of the least possible error. In establishing this result, we formally prove that a constant number of sensors suffice for a good estimate-an observation made by many researchers. We demonstrate the utility of this result in an experiment where 19 cameras are used to estimate the position of a target on a known plane. In the second part of this paper, we study relaxations of the problem formulation. We consider 1) a scenario where we are given a set of possible locations of the target (instead of a single estimate) and 2) relaxations of the sensing model. Note to Practitioners-This paper addresses a problem which arises in applications where many sensors are used to estimate the position of a target. For most sensing models, the estimates get better as the number of sensors increases. On the other hand, energy and communication constraints may render it impossible to use the measurements from all sensors. In this case, we face the sensor selection problem: how to select a "good" subset of sensors so as to obtain "good" estimates. We show that under a fairly restricted sensing model, a constant number of sensors are always competitive with respect to all sensors and present an algorithm for selecting such sensors. In obtaining this result, we assume that the sensor locations are known. In future research, we will investigate methods that are robust with respect to errors in sensor localization/calibration

We address the problem of selecting sensors so as to minimize the error in estimating the position of a target. We consider a generic sensor model where the measurements can be interpreted as polygonal, convex subsets of the plane. This model applies to a large class of sensors including cameras. We present an approximation algorithm which guarantees that the resulting error in estimation is within a factor 2 of the least possible error. In establishing this result, we formally prove that a constant number of sensors suffice for a good estimate-an observation made by many researchers. In the second part of the paper, we study the scenario where the target's position is given by an uncertainty region and present algorithms for both probabilistic and online versions of this problem.

In this paper, we present a computational framework for automatic generation of provably correct control laws for planar robots in polygonal environments. Using polygon triangulation and discrete abstractions, we map continuous motion planning and control problems, specified in terms of triangles, to computationally inexpensive problems on finite-state-transition systems. In this framework, discrete planning algorithms in complex environments can be seamlessly linked to automatic generation of feedback control laws for robots with underactuation constraints and control bounds. We focus on fully actuated kinematic robots with velocity bounds and (underactuated) unicycles with forward and turning speed bounds.

This paper contains two main results. First, we revisit the well-known visibility-based pursuit-evasion problem, and show that in contrast to deterministic strategies, a single pursuer can locate an unpredictable evader in any simply connected polygonal environment, using a randomized strategy. The evader can be arbitrarily faster than the pursuer, and it may know the position of the pursuer at all times, but it does not have prior knowledge of the random decisions made by the pursuer. Second, using the randomized algorithm, together with the solution to a problem called the "lion and man problem" as subroutines, we present a strategy for two pursuers (one of which is at least as fast as the evader) to quickly capture an evader in a simply connected polygonal environment. We show how this strategy can be extended to obtain a strategy for a polygonal room with a door, two pursuers who have only line-of-sight communication, and a single pursuer (at the expense of increased capture time).

Pursuit-evasion games in complex environments have a rich but disconnected history. Continuous or differential pursuit-evasion games focus on optimal control methods, and rely on very intense computations in order to provide locally optimal controls. Discrete pursuit-evasion games on graphs are algorithmically much more appealing, but completely ignore the physical dynamics of the players, resulting in possibly infeasible motions. In this paper, we present a provable and algorithmically feasible solution for visibility-based pursuit-evasion games in simply-connected environments, for players with dynamic constraints. This is achieved by combining two recent but distant results.

In this paper, we consider the problem of placing networked sensors in a way that guarantees coverage and connectivity. We focus on sampling based deployment and present algorithms that guarantee coverage and connectivity with a small number of sensors. We consider two different scenarios based on the flexibility of deployment. If deployment has to be accomplished in one step, like airborne deployment, then the main question becomes how many sensors are needed. If deployment can be implemented in multiple steps, then awareness of coverage and connectivity can be updated. For this case, we present incremental deployment algorithms, which consider the current placement to adjust the sampling domain. The algorithms are simple, easy to implement, and require a small number of sensors. We believe the concepts and algorithms presented in this paper provide a unifying framework for existing and future deployment algorithms, which consider many practical issues not considered in the present work.

We consider the problem of recovering an underwater image distorted by surface waves. A large amount of video data of the distorted image is acquired. The problem is posed in terms of finding an undistorted im- age patch at each spatial location. This challenging reconstruction task can be formulated as a manifold learning problem, such that the center of the manifold is the image of the undistorted patch. To compute the center, we present a new technique to estimate global distances on the manifold. Our technique achieves robustness through convex flow com- putations and solves the "leakage" problem inherent in recent manifold embedding techniques. 1 Introduction Consider the following problem. A pool of water is observed by a stationary video camera mounted above the pool and looking straight down. There are waves on the surface of the water and all the camera sees is a series of distorted images of the bottom of the pool, e.g. Figure 1. The aim is to use these images to recover the undistorted image of the pool floor as if the water was perfectly still. Besides obvious applications in ocean optics and underwater imaging [1], variants of this problem also arise in several other fields, including astronomy (overcoming atmospheric distortions) and structure-from-motion (learning the appearance of a deforming object). Most approaches to solve this problem try to model the distortions explicitly. In order to do this, it is critical not only to have a good parametric model of the distortion process, but also to be able to reliably extract features from the data to fit the parameters. As such, this approach is only feasible in well understood, highly controlled domains. On the opposite side of the spectrum is a very simple method used in underwater imaging: simply, average the data temporally. Although this method performs surprisingly well in many situations, it fails when the structure of the target image is too fine with respect to the amplitude of the wave (Figure 2). In this paper we propose to look at this difficult problem from a more statistical angle. We will exploit a very simple observation: if we watch a particular spot on the image plane, most of the time the picture projected there will be distorted. But once in a while, when the water just happens to be locally flat at that point, we will be looking straight down and seeing exactly the right spot on the ground. If we can recognize when this happens Authors in alphabetical order. Figure 1: Fifteen consecutive frames from the video. The experimental setup involved: a transparent bucket of water, the cover of a vision textbook "Computer Vision/A Modern Approach". Figure 2: Ground truth image and reconstruction results using mean and median and snap the right picture at each spatial location, then recovering the desired ground truth image would be simply a matter of stitching these correct observations together. In other words, the question that we will be exploring in this paper is not where to look, but when! 2 Problem setup Let us first examine the physical setup of our problem. There is a "ground truth" image G on the bottom of the pool. Overhead, a stationary camera pointing downwards is recording a video stream V . In the absence of any distortion V (x, y, t) = G(x, y) at any time t. However, the water surface refracts in accordance with Snell's Law. Let us consider what the camera is seeing at a particular point x on the CCD array, as shown in Figure 3(c) (assume 1D for simplicity). If the normal to the water surface directly underneath x is pointing straight up, there is no refraction and V (x) = G(x). However, if the normal is tilted by angle 1, light will bend by the amount 2 = 1 - sin-1 ( 1 sin 1.33 1 ), so the camera point V (x) will see the light projected from G(x + dx) on the ground plane. It is easy to see that the relationship between the tilt of the normal to the surface 1 and the displacement dx is approximately linear (dx 0.251h using small angle approximation, where h is the height of the water). This means that, in 2D, what the camera will be seeing over time at point V (x, y, t) are points on the ground plane sampled from a disk centered at G(x, y) and with radius related to the height of the water and the overall roughness of the water surface. A similar relationship holds in the inverse direction as well: a point G(x, y) will be imaged on a disk centered around V (x, y). What about the distribution of these sample points? According to Cox-Munk Law [2], the surface normals of rough water are distributed approximately as a Gaussian centered around the vertical, assuming a large surface area and stationary waves. Our own experiments, conducted by hand-tracking (Figure 3b), confirm that the distribution, though not exactly Gaussian, is definitely unimodal and smooth. Up to now, we only concerned ourselves with infinitesimally small points on the image or the ground plane. However, in practice, we must have something that we can compute with. Therefore, we will make an assumption that the surface of the water can be locally approximated by a planar patch. This means that everything that was true for points is now true for local image patches (up to a small affine distortion). 3 Tracking via embedding From the description outlined above, one possible solution emerges. If the distribution of a particular ground point on the image plane is unimodal, then one could track feature points in the video sequence over time. Computing their mean positions over the entire video will give an estimate of their true positions on the ground plane. Unfortunately, tracking over long periods of time is difficult even under favorable conditions, whereas our data is so fast (undersampled) and noisy that reliable tracking is out of the question (Figure 3(c)). However, since we have a lot of data, we can substitute smoothness in time with smoothness in similarity for a given patch we are more likely to find a patch similar to it somewhere in time, and will have a better chance to track the transition between them. An alternative to tracking the patches directly (which amounts to holding the ground patch G(x, y) fixed and centering the image patches V (x + dxt, y + dyt) on top of it in each frame), is to fix the image patch V (x, y) in space and observe the patches from G(x + dxt, y + dyt) appearing in this window. We know that this set of patches comes from a disk on the ground plane centered around patch G(x, y) our goal. If the disk was small enough compared to the size of the patch, we could just cluster the patches together, e.g. by using translational EM [3]. Unfortunately, the disk can be rather large, containing patches with no overlap at all, thus making only the local similarity comparisons possible. However, notice that our set of patches lies on a low-dimensional manifold; in fact we know precisely which manifold it's the disk on the ground plane centered at G(x, y)! So, if we could use the local patch similarities to find an embedding of the patches in V (x, y, t) on this manifold, the center of the embedding will hold our desired patch G(x, y). The problem of embedding the patches based on local similarity is related to the recent work in manifold learning [4, 5]. Basic ingredients of the embedding algorithms are: defin- ing a distance measure between points, and finding an energy function that optimally places them in the embedding space. The distance can be defined as all-pairs distance matrix, or as distance from a particular reference node. In both cases, we want the distance function to satisfy some constraints to model the underlying physical problem. The local similarity measure for our problem turned out to be particularly unreliable, so none of the previous manifold learning techniques were adequate for our purposes. In the following section we will describe our own, robust method for computing a global distance function and finding the right embedding and eventually the center of it. 1 N Surface h 2 G(x) G(x + dx) (a) (b) (c) Figure 3: (a) Snell's Law (b)-(c) Tracking points of the bottom of the pool: (b) the tracked position forms a distribution close to a Gaussian, (c): a vertical line of the image shown at different time instances (horizontal axis). The discontinuity caused by rapid changes makes the tracking infeasible. 4 What is the right distance function? Let I = {I1, . . . , In} be the set of patches, where It = V (x, y, t) and x = [xmin, xmax], y = [ymin, ymax] are the patch pixel coordinates. Our goal is to find a center patch to represent the set I. To achieve this goal, we need a distance function d : I I IR such that d(Ii, Ij) < d(Ii, Ik) implies that Ij is more similar to Ii than Ik. Once we have such a measure, the center can be found by computing: I = arg min d(Ii, Ij) (1) IiI Ij I Unfortunately, the measurable distance functions, such as Normalized Cross Correlation (N CC) are only local. A common approach is to design a global distance function using the measurable local distances and transitivity [6, 4]. This is equivalent to designing a global distance function of the form: d d(I local(Ii, Ij ), if dlocal(Ii, Ij) i, Ij ) = (2) dtransitive(Ii, Ij), otherwise. where dlocal is a local distance function, is a user-specified threshold and dtransitive is a global, transitive distance function which utilizes dlocal. The underlying assumption here is that the members of I lie on a constraint space (or manifold) S. Hence, a local similarity function such as N CC can be used to measure local distances on the manifold. An important research question in machine learning is to extend the local measurements into global ones, i.e. to design dtransitive above. One method for designing such a transitive distance function is to build a graph G = (V, E) whose vertices correspond to the members of I. The local distance measure is used to place edges which connect only very similar members of I. Afterwards, the length of pairwise shortest paths are used to estimate the true distances on the manifold S. For example, this method forms the basis of the well-known Isomap method [4]. Unfortunately, estimating the distance dtransitive(, ) using shortest path computations is not robust to errors in the local distances which are very common. Consider a patch that contains the letter A and another one that contains the letter B. Since they are different letters, we expect that these patches would be quite distant on the manifold S. However, among the A patches there will inevitably be a very blurry A that would look quite similar to a very blurry B producing an erroneous local distance measurement. When the transitive global distances are computed using shortest paths, a single erroneous edge will single- handedly cause all the A patches to be much closer to all the B patches, short-circuiting the graph and completely distorting all the distances. Such errors lead to the leakage problem in estimating the global distances of patches. This problem is illustrated in Figure 4. In this example, our underlying manifold S is a triangle. Suppose our local distance function erroneously estimates an edge between the corners of the triangle as shown in the figure. After the erroneous edge is inserted, the shortest paths from the top of the triangle leak through this edge. Therefore, the shortest path distances will fail to reflect the true distance on the manifold. 5 Solving the leakage problem Recall that our goal is to find the center of our data set as defined in Equation 1. Note that, in order to compute the center we do not need all pairwise distances. All we need is the quantity dI (Ii) = d(I I i, Ij ) for all Ii. j I The leakage problem occurs when we compute the values dI (Ii) using the shortest path metric. In this case, even a single erroneous edge may reduce the shortest paths from many different patches to Ii changing the value of dI(Ii) drastically. Intuitively, in order to prevent the leakage problem we must prevent edges from getting involved in many shortest path computations to the same node (i.e. leaking edges). We can formalize this notion by casting the computation as a network flow problem. Let G = (V, E) be our graph representation such that for each patch Ii I, there is a vertex vi V . The edge set E is built as follows: there is an edge (vi, vj) if dlocal(Ii, Ij) is less than a threshold. The weight of the edge (vi, vj) is equal to dlocal(Ii, Ij). To compute the value dI (Ii), we build a flow network whose vertex set is also V . All vertices in V - {vi} are sources, pushing unit flow into the network. The vertex vi is a sink with infinite capacity. The arcs of the flow network are chosen using the edge set E. For each edge (vj, vk) E we add the arcs vj vk and vk vj. Both arcs have infinite capacity and the cost of pushing one unit of flow on either arc is equal to the weight of (vj, vk), as shown in Figure 4 left (top and bottom). It can easily be seen that the minimum cost flow in this network is equal to dI (Ii). Let us call this network which is used to compute dI (Ii) as N W (Ii). The crucial factor in designing such a flow network is choosing the right cost and capacity. Computing the minimum cost flow on N W (Ii) not only gives us dI(Ii) but also allows us to compute how many times an edge is involved in the distance computation: the amount of flow through an edge is exactly the number of times that edge is used for the shortest path computations. This is illustrated in Figure 4 (box A) where d1 units of cost is charged for each unit of flow through the edge (u, w). Therefore, if we prevent too much flow going through an edge, we can prevent the leakage problem. d3/ d1/ d Error u 2/c2 w u w d1 v A: Shortest Path B: Convex Flow c d1/c1 1 c1 + c2 u C: Shortest Path with Capacity Error d/ d1/c1 v u w v c1 w Figure 4: The leakage problem. Left: Equivalence of shortest path leakage and uncapacitated flow leakage problem. Bottom-middle: After the erroneous edge is inserted, the shortest paths from the top of the triangle to vertex v go through this edge. Boxes A-C:Alternatives for charging a unit of flow between nodes u and w. The horizontal axis of the plots is the amount of flow and the vertical axis is the cost. Box A: Linear flow. The cost of a unit of flow is d1 Box B: Convex flow. Multiple edges are introduced between two nodes, with fixed capacity, and convexly increasing costs. The cost of a unit of flow increases from d1 to d2 and then to d3 as the amount of flow from u to w increases. Box C: Linear flow with capacity. The cost is d1 until a capacity of c1 is achieved and becomes infinite afterwards. One might think that the leakage problem can simply be avoided by imposing capacity constraints on the arcs of the flow network (Figure 4, box C). Unfortunately, this is not very easy. Observe that in the minimum cost flow solution of the network N W (Ii), the amount of flow on the arcs will increase as the arcs get closer to Ii. Therefore, when we are setting up the network N W (Ii), we must adaptively increase the capacities of arcs "closer" to the sink vi otherwise, there will be no feasible solution. As the structure of the graph G gets complicated, specifying this notion of closeness becomes a subtle issue. Further, the structure of the underlying space S could be such that some arcs in G must indeed carry a lot of flow. Therefore imposing capacities on the arcs requires understanding the underlying structure of the graph G as well as the space S which is in fact the problem we are trying to solve! Our proposed solution to the leakage problem uses the notion of a convex flow. We do not impose a capacity on the arcs. Instead, we impose a convex cost function on the arcs such that the cost of pushing unit flow on arc a increases as the total amount of flow through a increases. See Figure 4, box B. This can be achieved by transforming the network N W (Ii) to a new network N W (Ii). The transformation is achieved by applying the following operation on each arc in N W (Ii): Let a be an arc from u to w in N W (Ii). In N W (Ii), we replace a by k arcs a1, . . . , ak. The costs of these arcs are chosen to be uniformly increasing so that cost(a1) < cost(a2) < . . . < cost(ak). The capacity of arc ak is infinite. The weights and capacities of the other arcs are chosen to reflect the steepness of the desired convexity (Figure 4, box B). The network shown in the figure yields the following function for the cost of pushing x units of flow through the arc: d1x, if 0 x c1 cost(x) = d1c1 + d2(x - c1), if c1 x c2 (3) d1c1 + d2(c2 - c1) + d3(x - c1 - c2), if c2 x The advantage of this convex flow computation is twofold. It does not require putting thresholds on the arcs a-priori. It is always feasible to have as much flow on a single arc as required. However, the minimum cost flow will avoid the leakage problem because it will be costly to use an erroneous edge to carry the flow from many different patches. 5.1 Fixing the leakage in Isomap As noted earlier, the Isomap method [4] uses the shortest path measurements to estimate a distance matrix M . Afterwards, M is used to find an embedding of the manifold S via MDS. As expected, this method also suffers from the leakage problem as demonstrated in Fig- ure 5. The top-left image in Figure 5 shows our ground truth. In the middle row, we present an embedding of these graphs computed using Isomap which uses the shortest path length as the global distance measure. As illustrated in these figures, even though isomap does a good job in embedding the ground truth when there are no errors, the embedding (or manifold) collapses after we insert the erroneous edges. In contrast, when we use the convex-flow based technique to estimate the distances, we recover the true embedding even in the presence of erroneous edges (Figure 5 bottom row).

In this paper, we study the Vapnik-Chervonenkis (VC)-dimension of set systems arising in 2D polygonal and 3D polyhedral configurations where a subset consists of all points visible from one camera. In the past, it has been shown that the VC-dimension of planar visibility systems is bounded by 23 if the cameras are allowed to be anywhere inside a polygon without holes. Here, we consider the case of exterior visibility, where the cameras lie on a constrained area outside the polygon and have to observe the entire boundary. We present results for the cases of cameras lying on a circle containing a polygon (VC-dimension= 2) or lying outside the convex hull of a polygon (VC-dimension= 5). The main result of this paper concerns the 3D case: We prove that the VC-dimension is unbounded if the cameras lie on a sphere containing the polyhedron, hence the term exterior visibility.

Mapping an environment with an imaging sensor becomes very challenging if the environment to be mapped is unknown and has to be explored. Exploration involves the planning of views so that the entire environment is covered. The majority of implemented mapping systems use a heuristic planning while theoretical approaches regard only the traveled distance as cost. However, practical range acquisition systems spend a considerable amount of time for acquisition. In this paper, we address the problem of minimizing the cost of looking around a corner, involving the time spent in traveling as well as the time spent for reconstruction. Such a local exploration can be used as a subroutine for global algorithms. We prove competitive ratios for two online algorithms. Then, we provide two representations of local exploration as a Markov Decision Process and apply a known policy iteration algorithm. Simulation results show that for some distributions the probabilistic approach outperforms deterministic strategies.

In this paper, we investigate data fusion techniques for target tracking using distributed sensors. Specifically, we are interested in how pairs of bearing or range sensors can be best assigned to targets in order to minimize the expected error in the estimates. We refer to this as the focus of attention (FOA) problem. In its general form, FOA is NP-hard and not well approximable. However, for specific geometries we obtain significant approximation results: a 2-approximation algorithm for stereo cameras on a line, a PTAS for when the cameras are equidistant, and a 1.42 approximation for equally spaced range sensors on a circle. By reposing as a maximization problem - where the goal is to maximize the number of tracks with bounded error - we are able to leverage results from maximum set-packing to render the problem approximable. We demonstrate the results in simulation for a target tracking task, and for localizing a team of mobile agents in a sensor network. These results provide insights into sensor/target assignment strategies, as well as sensor placement in a distributed network.

In an immersive tele-presence environment a 3D remote real scene is projected from the viewpoint of the local user. This 3D world is acquired through stereo reconstruction at the remote site. In this paper we start a performance analysis of stereo algorithms with respect to the task of immersive visualization. As opposed to usual monocular image based rendering, we are also interested in the depth error in novel views because our rendering is stereoscopic. We describe an evaluation test-bed which provides a world-wide first available set of registered dense "ground-truth" laser data and image data from multiple views. We establish metrics for novel depth views that reflect discrepancies both in the image and in 3D-space. It is well known that stereo performance is affected by both erroneous matching as well as incorrect depth triangulation. We experimentally study the effects of occlusion and low texture on the distributions of the error metrics. Then, we algebraically predict the behavior of depth and novel projection error as a function of the camera set-up and the error in the disparity. These are first steps towards building a laboratory for psychophysical judgement of depth estimates which is the ultimate performance test of tele-presence stereo.