Browsing by Author "Isler, Volkan"

Now showing 1 - 20 of 23

A Pursuit-Evasion Toolkit
(2015-07-24) Noori, Narges; Beveridge, Andrew; Isler, Volkan
This tutorial contains tools and techniques for designing pursuit and evasion strategies. The material targets a diverse audience including STEM educators as well as robotics researchers interested in applications of pursuit-evasion games. We start with a simple "lion and man" game in a square environment which should be accessible to anyone with a high-school level background on geometry and trigonometry. We then visit various versions of this game with increasing complexity. Rather than surveying specific results for specific environments, the tutorial highlights broadly applicable techniques and strategies. It also includes exercises for STEM educators as well as open problems for robotics researchers.
Adaptive View Planning for Aerial 3D Reconstruction
(2018-09-17) Peng, Cheng; Isler, Volkan
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 tobuild a coarse proxy to the scene. We then present (i)~a method that builds a set of adaptive viewing planes for efficient view selectionand (ii)~an algorithm to plan a trajectory that guarantees high reconstruction quality which does not deviates 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.
Aerial Radio-based Telemetry for Tracking Wildlife
(2017-04-10) Bayram, Haluk; Stefas, Nikolaos; Isler, Volkan
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 antenna and USB receiver to capture the signal. It uses its own movement to obtain a bearing measurement. The uncer-tainty in these measurements is assumed to be bounded and represented as wedges. The measurements are then merged by intersecting the wedges. The localization un-certainty 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. We also validate the strategy in simulations and in field experiments over a 5 hectare area using an autonomous aerial robot equipped with a directional antenna.
An Approximation Algorithm for Online Coverage Path Planning with the Energy Constraint
(2019-06-17) Wei, Ming; Isler, Volkan
In online coverage path planning, the objective is to plan paths for a robot to visit every point in an unknown environment as quickly as possible. We consider online coverage with an energy constraint which is modeled as the maximum distance B the robot can travel after a full recharge. There is a single charging station in the environment which needs to be revisited before the robot runs out of energy. Under this model, it has been proven that any algorithm for online coverage path planning with the energy constraint must have an approximation rate of ?(log B/4r) [1], where r is the robot diameter. In this paper, we present an optimal online algorithm whose worst-case performance matches this lower bound asymptotically. We present simulations and field experiments which demonstrate the applicability of our algorithm in real applications.
Approximation Algorithms for Tours of Orientation-varying View Cones
(2018-02-16) Stefas, Nikolaos; Plonski, Patrick A.; Isler, Volkan
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 ? we have the tilted Cone-TSPN problem, to which we present a polynomial time approximation algorithm. 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.
Asynchronous Network Formation in Unknown Unbounded Environments
(2018-09-17) Engin, Selim; Isler, Volkan
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{M H}})$ 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.
Constrained Probabilistic Search for a One-Dimensional Random Walker
(2015-12-21) Noori, Narges; Renzaglia, Alessandro; Vander Hook, Joshua; Isler, Volkan
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 the line: 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 they are on the same node or if they take the same edge at the same time. In the crossing model, detection happens only if they land 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 which 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.
Coverage path planning under the energy constraint
(2018-02-16) Isler, Volkan; Wei, Minghan
In coverage applications, a common assumption is that the robot can fully cover the environment without recharging. However, in reality most mobile robot systems operateunder 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 polygonal grids with a single charging station. Energy consumption throughout the environment is assumed to be uniform and proportional to the distance traveled. We present the first constant-factor approximation algorithm for contour-connected environments. We further extend the algorithm for general environments. We also validate the resultsin experiments performed with an aerial robot.
Environment and Solar Map Construction for Solar-Powered Mobile Systems
(2015-04-16) Plonski, Patrick A.; Vander Hook, Joshua; Isler, Volkan
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 which 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.
Gathering Bearing Data for Target Localization
(2015-09-28) Bayram, Haluk; Vander Hook, Joshua; Isler, Volkan
We consider the problem of gathering bearing data in order to localize targets. We start with a commonly used notion of uncertainty based on Geometric Dilution of Precision (GDOP) and study the following bi-criteria problem. Given a set of potential target locations and an uncertainty level U, compute an ordered set of measurement locations for a single robot which (i) minimizes the total cost given by the travel time plus the time spent in taking measurements, and (ii) ensures that the uncertainty in estimating the target’s location is at most U regardless of the targets’ locations. We present an approximation algorithm and prove that its cost is at most 28.9 times the optimal cost while guaranteeing that the uncertainty is at most 5.5U. In addition to theoretical analysis, we validate the results in simulation and experiments performed with a directional antenna used for tracking invasive fish.
Large Scale Image Mosaic Construction for Agricultural Applications
(2016-01-28) Li, Zhengqi; Isler, Volkan
We present a novel technique for stitching images including those obtained from aerial vehicles flying at low altitudes. Existing image stitching/mosaicking methods rely on inter-image homography computation based on a planar scene assumption. This assumption holds when images are taken from high-altitudes (hence the depth variation is negligible). It is often violated when flying at low altitudes. Further, to avoid scale and resolution changes, existing methods rely on primarily translational motion at fixed altitudes. Our method removes these limitations and performs well even when aerial images are taken from low altitudes by an aerial vehicle performing complex motions. It starts by extracting the ground geometry from a sparse reconstruction of the scene obtained from a small fraction of the input images. Next, it selects the best image (from the entire sequence) for each location on the ground using a novel camera selection criterion. This image is then independently rectified to obtain the corresponding portion of the mosaic. Therefore, the technique avoids performing costly joint-optimization over the entire sequence. It is validated using challenging input sequences motivated by agricultural applications. For videos and data please visit: Image Mosaic Generation RSN page.
Line-of-sight pursuit in strictly sweepable polygons
(University of Minnesota. Institute for Mathematics and Its Applications, 2015-08) Berry, Lindsay; Beveridge, Andrew; Butterfield, Jane; Isler, Volkan; Keller, Zachary; Shine, Alana; Wang, Junyi
MinneApple: A Benchmark Dataset for Apple Detection and Segmentation
(2019-09-11) Haeni, Nicolai; Roy, Pravakar; Isler, Volkan; haeni001@umn.edu; Haeni, Nicolai; University of Minnesota Robotic Sensor Network Laboratory
We present a new dataset with the goal of advancing the state-of-the-art in fruit detection, segmentation, and counting in orchard environments. We hope to achieve this by providing a large variety of high-resolution images acquired in orchards, together with human annotations of the fruits on the trees. Objects are labeled using polygon masks for each object instance to aid in precise object detection, localization or segmentation. Additionally, we provide data for patch-based counting of clustered fruits. Our dataset contains over 40'000 annotated object instances in 1000 images.
Navigation Around an Unknown Obstacle for Autonomous Surface Vehicles Using a Forward-Facing Sonar
(2015-04-16) Plonski, Patrick A.; Vander Hook, Joshua; Peng, Cheng; Noori, Narges; Isler, Volkan
A robotic boat is moving between two points when it encounters an obstacle of unknown size. The boat must find a short path around the obstacle to resume its original course. How should the boat move when it can only sense the proximity of the obstacle, and does not have prior information about the obstacle’s size? We study this problem for a robotic boat with a forward-facing sonar. We study two versions of the problem. First, we solve a simplified case when the obstacle is a rectangle of known orientation but unknown dimensions. Second, we study a more general case where an arbitrarily shaped obstacle is contained between two known parallel lines. We study the performance of the algorithms analytically using competitive analysis and present results from field experiments. The experimental setup is relevant for harbor patrol or autonomous navigation in shallow water.
Pursuit and Evasion with Uncertain Bearing Measurements
(2014-01-07) Vander Hook, Joshua; Isler, Volkan
We study pursuit-evasion games in which a pursuer tries to capture an evader by moving on to the evader’s current location. We investigate how sensing capability of the pursuer affects the game outcome. In particular, we consider a pursuer which can sense only the bearing to an evader. Furthermore, there is noise in the measurements in such a way that an adversary may adjust each bearing measured by an angle up to ? away from the true value. In this work, we study two classical pursuit evasion games under bearing uncertainty. In the first game, played on the open plane, the pursuer tries to maintain the distance to an evader with equal speed. If the pursuer has full knowledge of the evaders location the pursuer can maintain the separation between the players by moving toward the evader. However, when an adversarial sensing model is introduced, we show that for any pursuer strategy, the evader can increase the distance to the pursuer indefinitely. The rate at which the distance increases is linear in time. ?. In the second game, both players are inside a bounded circular area. This version is known as the Lion-and-Man game, and has been well studied when no sensing limitations are imposed. In particular, the pursuer (Lion) is known to have an O(rlogr) strategy to capture the evader, where r is the radius of the circle. In contrast, when sensing uncertainty is introduced, we show that for any ? > 0, there exist environments in which the man can evade capture indefinitely.
Registering Reconstructions of the Two Sides of Fruit Tree Rows
(2018-04-10) Roy, Pravakar; Dong, Wenbo; Isler, Volkan
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 multiplesimulated and real datasets.
Robotic Surveying of Apple Orchards
(2015-06-18) Roy, Pravakar; Stefas, Nikolaos; Peng, Cheng; Bayram, Haluk; Tokekar, Pratap; Isler, Volkan
We present a novel system for surveying apple orchards by counting apples and estimating apple diameters. Existing surveying systems resort to active sensors, or high-resolution close-up images under controlled lighting conditions. The main novelty of our system is the use of a traditional low resolution stereo-system mounted on a small aerial vehicle. Vision processing in this set up is challenging because apples occupy a small number of pixels and are often occluded by either leaves or other apples. After presenting the system setup and our view-planning methodology, we present a method to match and combine multiple views of each apple to circumvent these challenges and report results from field trials. We conclude the paper with an experimental analysis of the diameter estimation error.
Sensor Planning for a Symbiotic UAV and UGV system for Precision Agriculture
(2013-03-25) Tokekar, Pratap; Vander Hook, Joshua; Mulla, David; Isler, Volkan
We study the problem of coordinating an Unmanned Aerial Vehicle (UAV) and Unmanned Ground Vehicle (UGV) to collect data for a precision agriculture application. In this application, the ground and aerial measurements collected by the system are used for estimating Nitrogen~(N) levels across a field. These estimates in turn guide fertilizer application. The capability to apply the right amount of fertilizer at the right time can drastically reduce fertilizer usage which is desirable from an environmental and economic standpoint. We propose to use a symbiotic UAV and UGV system in which the UGV is capable of muling the UAV to a deployment location and picking it up later. This would allow the system to overcome the short battery life of a typical UAV. Toward building such a system, the paper makes the following contributions: We start with a prior N-distribution (which can be obtained from a satellite image) over the field. The goal is to classify each point into a fixed number of classes indicating N-stress levels. First, we present a method to identify Potentially Mislabeled (PML) points which are points whose probability of being mislabeled is above a threshold. Second, we study the problem of planning the UAV path so that it can visit the maximum number of PML points subject to its energy budget. The novelty of the formulation is the capability of the UGV to mule the UAV to deployment points. Third, we introduce a new path planning problem in which the UGV must take a measurement near each PML point visited by the UAV. The goal is to minimize the total time spent in traveling and taking measurements. For both problems, we present constant-factor approximation algorithms. Finally, we demonstrate the utility of the system and our algorithms with simulations which use manually collected data from the field as well as realistic energy models for the UAV and the UGV.
Snakes in a Plant: 3D Reconstruction of Foliage using Tethered Active Contours
(2018-06-15) Plonski, Patrick A.; Isler, Volkan
We present a novel method for reconstructing 3D models of foliage from a pair of images. Leaves are especially challenging objects to reconstruct in natural settings because of the lack of distinct features. We present a novel method for simultaneously growing contours to detect leaf boundaries. We then compute the transformation between the leaves to generate disparity maps. We demonstrate the effectiveness of our method on challenging instances where standard reconstruction methods fail.
Tree Morphology for Phenotyping from Semantics-Based Mapping in Orchard Environments
(2018-03-02) Dong, Wenbo; Isler, Volkan
Measuring tree morphology for phenotyping is an essential but labor-intensive activity in horticulture. Researchers often rely on manual measurements which may not be accurate for example when measuring tree volume. Recent approaches on automating the measurement process rely on LIDAR measurements coupled with high-accuracy GPS. Usually each side of a row is reconstructed independently and then merged using GPS information. Such approaches have two disadvantages: (1) they rely on specialized and expensive equipment, and (2) since the reconstruction process does not simultaneously use information from both sides, side reconstructions may not be accurate. We also show that standard loop closure methods do not necessarily align tree trunks well. In this paper, we present a novel vision system that employs only an RGB-D camera to estimate morphological parameters. A semantics-based mapping algorithm merges the two-sides 3D models of tree rows, where integrated semantic information is obtained and refined by robust fitting algorithms. We focus on measuring tree height, canopy volume and trunk diameter from the optimized 3D model. Experiments conducted in real orchards

University Digital Conservancy

Browse by Author

Browsing by Author "Isler, Volkan"