This paper addresses the challenge of coordinating multi-robot teams to complete complex tasks efficiently when task-relevant object locations are initially unknown. The proposed approach integrates learning-based estimation of uncertain environmental aspects with model-based planning to enable long-horizon coordination across 1, 2, and 3 robot teams. The method focuses on reasoning about likely object locations, evaluating individual action contributions to overall task progress, and dynamically coordinating team efforts under uncertainty. Experimental results demonstrate efficient multi-stage task planning performance compared to competitive baselines in large problem domains.