Path planning algorithms for robots in a data muling system
2010-12
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Path planning algorithms for robots in a data muling system
Authors
Published Date
2010-12
Publisher
Type
Thesis or Dissertation
Abstract
We study two path planning problems that arise in data muling systems where robots
are charged to collect data from wireless devices dispersed across a large environment.
In such applications, deploying a network of stationary wireless sensors may be infeasible
when many relay nodes are deployed to ensure connectivity. Instead, a few robots can
be used as data mules to collect data from these devices.
The first problem studied in this thesis is to find tours for multiple robots so as
to collect data from all sensors in the least amount of time. We refer to this problem
as the Data Gathering Problem (DGP). We assume that sensors have a uniform disk
communication model. In this model, data can be downloaded from a sensor with
fixed rate inside its communication disk. We present an optimal algorithm for the one
dimensional version of DGP. For the two dimensional version we present a constant
factor approximation algorithm. Afterwards, we present field experiments in which an
autonomous robotic data mule collects data from sensor nodes deployed over a large
area.
Next, we study data collection problem with a more realistic communication model
for sensors. In experiments we found that the time taken to download data from a
sensor s is a function of the locations of the robot and s: If the robot is a distance
rin away from s, it can download the sensor’s data reliably in Tin units of time. If the
distance is greater than rin but less than rout , robot can still download data but due to
higher packet loss probability the average download time Tout is higher (Tout > Tin). We
refer to this model as the Two-Ring communication model and the corresponding path
planning problem as the Two-Ring Tour (TRT) problem. We present a constant factor
approximation algorithm for the general case. The algorithm uses a polynomial time
approximation scheme as a subroutine. Though the scheme has polynomial running
time, its running time is impractically large. It is also very complex to implement.
Therefore we study special cases of the TRT problem and present efficient algorithms
for them.
For robotic data mules to be useful, the robots must be capable of operating in the
field for extended periods of time. Therefore, in the last part of the thesis we initiate
ii
the study of solar energy harvesting for robotic navigation. Our primary contribution
is an experimental model of energy consumption and harvesting as a function of environmental
parameters. We demonstrate the utility of this model in a simple navigation
task.
Keywords
Description
University of Minnesota M.S. thesis. December 2010. Major: Computer Science and Engineering. Advisor: Prof. Volkan Isler. 1 computer file (PDF); viii, 66 pages.
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Bhadauria, Deepak. (2010). Path planning algorithms for robots in a data muling system. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/104135.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.