Learning in Human and Robot Search: Subgoal, Submodularity, and Sparsity
2016-08
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Learning in Human and Robot Search: Subgoal, Submodularity, and Sparsity
Authors
Published Date
2016-08
Publisher
Type
Thesis or Dissertation
Abstract
Search is an essential technology for various robotic applications and it is also central to human daily activities. Searching for targets efficiently consists of NP-hard problems, but young children can search for targets very efficiently . How humans search for targets efficiently is still a mystery. Hence, two central questions are as follows: First, how do humans search for targets efficiently ? Second, how can robots learn to search like humans? The central goal of this dissertation is to explore these two questions, analyzing and modeling human search behavior and then applying the findings to robot search. This thesis is organized in three parts--human search analysis, problem reformulation, and learning in robot search. In the first part, the goal is to analyze and model human search behavior. In the experiments, human subjects remotely control a mobile robot to search for a target through teleoperation. Their search data are collected for further analysis. A novel framework consisting structure learning and K-means clustering is proposed to model and analyze humans search behavior. The analysis of the experimental data demonstrates that (1) humans are able to solve the complex search task by breaking it up into smaller tasks (so called subgoal hypothesis); and (2) humans consider both coverage and motion cost while searching. In the second part, the goal is to derive an objective function considering coverage and motion cost. The objective of search is to maximize the probability of target detection while covering most of the environment in minimum time. The robot needs to consider three objectives: (1) maximal coverage; (2) maximal probability of detection; and (3) minimum-time trajectory planning. However, all these objectives are NP-hard. Since two of these objective functions are submodular, the search problem can be reformulated as maximizing the cumulative probability of detection (PD) with motion cost. The proof shows that greedy algorithms give near-optimal subgoals with high probability. In the last part, the approach is to learn to search through sequential perception and actions. Since the PD function and cost-to-go (CTG) function depend on the environment, the robot needs to learn both the PD function and CTG function. To make the learning process of the PD function tractable, a technique based on Spatial Fourier Sparse Set (SFSS) is proposed that takes advantage of the structure in the relationship between the robot's spatial conguration and its environmental sensing. Q-learning is proposed to learn the CTG function. The learned PD and CTG functions can then be used to generate subgoals for search tasks. Based on compressed sensing theory, the proposed SFSS is able to learn a submodular function with m samples, where m <= O(klog(b)), b is the Fourier basis number and k is the number of nonzero Fourier coecients. The proposed algorithms generate near-optimal subgoals for both human and robot search experiments. Human experiments showed that the human search performance is improved with the assistance of subgoals. Robot experiments demonstrated that the robot can search for the target faster than any existing approaches. To the best of our knowledge, this is the first work that theorems and experiments prove that humans cannot outperform robots since the objective functions of search problems are submodular.
Description
University of Minnesota Ph.D. dissertation. August 2016. Major: Computer Science. Advisors: Berenice Mettler, Maria Gini. 1 computer file (PDF); xi, 97 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Tseng, Kuo-Shih. (2016). Learning in Human and Robot Search: Subgoal, Submodularity, and Sparsity. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/183325.
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.