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 talk is to answer these two questions. This talk is organized in three parts–human search analysis, learning in robot search, and other potential applications.
The key concepts of this talk are subgoal, submodularity, and sparsity. First, the human search analysis shows that humans' search motion can be represented by a few subgoals. Second, since the motion is divided into discrete subgoals and the objective functions have submodularity, the greedy algorithms generate near-optimal subgoals. Third, although learning submodular functions is a challenge, the sparsity in the Fourier domain makes it feasible. Hence, a robot can learn how to search for a target via these properties.
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 on search problems.