Many complex domains would benefit from the services of Large-scale, Safety-verified, Always-on (LSA) robotic systems. However, existing large-scale solutions often forego the complex reasoning required for safety verification and prescient reasoning in favour of scalability. We propose a method of partitioning the task domain to enable scalability, inspired by a ‘problem-first’ solution paradigm. Our method decomposes a large, intractable problem into a set of smaller, tractable sub-problems by spatially dividing the task domain into maximally-independent sub-domains. We present experimental evidence of the benefits of this approach in the context of a nuclear maintenance system.