Path planning for mobile robots during map construction requires the consideration of not only traversal costs but also belief state deformation, both of which have been studied independently. We therefore introduce a method for planning safe paths over cost maps given the Maximum Expected Deformation (MED) over the entire belief state. A process akin to convoluting the cost map is applied, whereby the cost map is dilated by a kernel whose size varies as a function of the MED at each point in the map. The dilated cost map is then used to generate the optimal policy that is guaranteed to be safe in the presence of map deformation. A traditional EKF-SLAM process was simulated and the resulting belief state used to both calculate the feasibility of a given path and the optimal policy for minimising traversal cost.