  In many robotic domains such as flexible automated manufacturing or personal
assistance, a fundamental perception task is that of identifying and localizing
objects whose 3D models are known. Canonical approaches to this problem include
discriminative methods that find correspondences between feature descriptors
computed over the model and observed data. While these methods have been
employed successfully, they can be unreliable when the feature descriptors fail
to capture variations in observed data; a classic cause being occlusion. As a
step towards deliberative reasoning, we present PERCH: PErception via SeaRCH,
an algorithm that seeks to find the best explanation of the observed sensor
data by hypothesizing possible scenes in a generative fashion. Our
contributions are: i) formulating the multi-object recognition and localization
task as an optimization problem over the space of hypothesized scenes, ii)
exploiting structure in the optimization to cast it as a combinatorial search
problem on what we call the Monotone Scene Generation Tree, and iii) leveraging
parallelization and recent advances in multi-heuristic search in making
combinatorial search tractable. We prove that our system can guaranteedly
produce the best explanation of the scene under the chosen cost function, and
validate our claims on real world RGB-D test data. Our experimental results
show that we can identify and localize objects under heavy occlusion--cases
where state-of-the-art methods struggle.
