In this paper, we present a system for autonomous object search and exploration in cluttered environments. The system shortens the average time needed to complete search tasks by continually planning multiple perception actions ahead of time using probabilistic prior knowledge. Useful sensing actions are found using a frontier-based view sampling technique in a continuously built 3D map. We demonstrate the system on real hardware, investigate the planner’s performance in three experiments in simulation, and show that our approach achieves shorter overall run times of search tasks compared to a greedy strategy.