In automated manufacturing, robots must reliably assemble parts of various geometries and low tolerances. Ideally, they plan the required motions autonomously. This poses a substantial challenge due to high-dimensional state spaces and non-linear contact-dynamics. Furthermore, object poses and model parameters, such as friction, are not exactly known and a source of uncertainty. The method proposed in this paper models the task of parts assembly as a belief space planning problem over an underlying impedance-controlled, compliant system. To solve this planning problem we introduce an asymptotically optimal belief space planner by extending an optimal, randomized, kinodynamic motion planner to non-deterministic domains. Under an expansiveness assumption we establish probabilistic completeness and asymptotic optimality. We validate our approach in thorough, simulated and real-world experiments of multiple assembly tasks. The experiments demonstrate our planners ability to reliably assemble objects, solely based on CAD models as input.