Browsing by Author "Tokekar, Pratap"

Now showing 1 - 10 of 10

Bearing-Only Active Target Localization Strategies for a System of Two Communicating Mobile Robots: Full Technical Report
(2013-04-08) Vander Hook, Joshua; Tokekar, Pratap
We study the problem of locating a stationary target using two 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. Further, the robots are subject to distance-based communication constraints. We first study properties of an optimal strategy which has access to the target's true location. It turns out that under certain circumstances, the optimal algorithm will break communication to take measurements and rendezvous to merge them. Using these insights, we design an online strategy (which does not have access to the target's true location) and show that the strategy can locate the target up to a desired uncertainty level at near-optimal cost. The results are applicable to other bearing sensors with non-zero measurement cost, such as pan- tilt cameras. In addition to theoretical analysis, we validate the algorithm in simulations and field experiments performed using autonomous surface vehicles. This full version includes proofs which are not included in the conference version.
Cautious Greedy Strategy for Bearing-based Active Localization: Technical Report
(2011-09-16) Vander Hook, Joshua; Tokekar, Pratap
We study a novel sensing model which occurs in wildlife monitoring applications. The sensor can be approximated as a bearing-to-target sensor, but with several critical attributes that set it apart from those addressed in bearing-only tracking literature. We propose a measurement strategy that can guarantee reduction in uncertainty in competitive time, regardless of the problem instance. We provide theoretical analysis in the form of a competitive proof, numerical studies, and results from field trials which confirm the applicability of the algorithm.
Energy Optimal Velocity Profiles for Car-like Robots
(2011-02-09) Tokekar, Pratap; Karnad, Nikhil
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 energy-efficient velocity profiles for car-like robots given a path to travel. We start with an established model for energy consumption of DC motors. First, we study the problem of computing an optimal velocity profile for a car-like robot so as to minimize the energy consumed while traveling along a given path. 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.
Energy-Optimal Trajectory Planning for Car-Like Robots
(2013-04-08) Tokekar, Pratap; Karnad, Nikhil
When a battery-powered robot needs to operate for a long period of time, optimizing its energy consumption becomes critical. Driving motors are a major source of power consumption for mobile robots. In this paper, we study the problem of finding optimal paths and velocity profiles for car-like robots so as to minimize the energy consumed during motion. We start with an established model for energy consumption of DC motors. We first study the problem of finding the energy optimal velocity profiles, given a path for the robot. We present closed form solutions for the unconstrained case and for the case where there is a bound on maximum velocity. We then study a general problem of finding an energy optimal path along with a velocity profile, given a starting and goal position and orientation for the robot. Along the path, the instantaneous velocity of the robot may be bounded as a function of its turning radius, which in turn affects the energy consumption. Unlike minimum length paths, minimum energy paths may contain circular segments of varying radii. We show how to efficiently construct a graph which generalizes Dubins' paths by including segments with arbitrary radii. Our algorithm uses the closed-form solution for the optimal velocity profiles as a subroutine to find the minimum energy trajectories, up to a fine discretization. We investigate the structure of energy-optimal paths and highlight instances where these paths deviate from the minimum length Dubins' curves. In addition, we present a calibration method to find energy model parameters. Finally, we present results from experiments conducted on a custom-built robot for following optimal velocity profiles.
Long-Term Search Through Energy Efficiency and Harvesting
(2013-01-09) Noori, Narges; Plonski, Patrick A.; Renzaglia, Alessandro; Tokekar, Pratap; VanderHook, Joshua
We study a search problem motivated by our ongoing work on finding radio-tagged invasive fish with an Autonomous Surface Vehicle (ASV). We focus on settings where the fish tend to move along the boundary of a lake. This setting allows us to formulate the problem as a one-dimensional search problem in which the searcher chooses between station keeping and moving so as to maximize the probability of finding the target in a given amount of time without violating its energy-budget. We model the movement of the target as a random-walk and present a closed-form solution for this search problem. Next, we investigate how long-term autonomy can be enabled by energy harvesting. In this case, the search strategy should incorporate the amount of solar energy available at a particular location and particular time. We show how this quantity can be predicted by estimating the geometry of the tree line along the shore. We then obtain the optimal strategy which maximizes the probability of finding the target by formulating the problem as finding the optimal strategy for a Markov Decision Process. Data collected from field experiments validate our approach.
Multi-Target Visual Tracking with Aerial Robots
(2014-06-20) Tokekar, Pratap; Franchi, Antonio
We study the problem of tracking mobile targets using a team of aerial robots. The robots are mounted with cameras that face downwards, and are used 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, thus potentially covering a larger number of targets but with lower 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 a weighted, combinatorial optimization problem. A greedy algorithm yields a 1/2 approximation for this problem. Finally, we evaluate the algorithm and the sensing model through simulations and preliminary experiments.
Polygon Guarding with Orientation
(2014-01-03) Tokekar, Pratap
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 a good view of an object from all orientations is viewed as an important requirement for surveillance and visual tracking applications. We study the art gallery problem under a constraint, termed triangle-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 $Omega(sqrt{n})$ guards are always necessary for triangle-guarding the interior of a simple polygon having n vertices. Next, we study the problem of triangle-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.
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 Placement and Selection for Bearing Sensors with Bounded Uncertainty
(2012-02-24) Tokekar, Pratap
We consider the problem of placing sensors so as to effectively localize a target in a square workspace. In our model, each sensor returns a bearing measurement with bounded error: the true location of the target is guaranteed to be contained in a 2?-wedge around the measurement where ? is a sensor noise parameter. The target is localized by intersecting the measurements (wedges) from all sensors. The estimation quality is given by the area of the intersection. We show that by placing sensors on a triangular grid, one can guarantee that the estimation quality is within a constant factor of the quality that can be achieved by any placement in the worst-case (regardless of target’s location and measurements obtained). We also show that this estimate can be obtained by activating a small number of sensors and thereby provide a mechanism for sensor selection as well.
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.

University Digital Conservancy

Browse by Author

Browsing by Author "Tokekar, Pratap"