In this letter, an approach is presented to estimate the stiffness characteristics of elastically deformable objects, while being processed in a robotic cleaning system. Building on our previous work [J. D. Langsfeld, A. M. Kabir, K. N. Kaipa, and S. K. Gupta, “Robotic bimanual cleaning of deformable objects with online learning of part and tool models,” in Proc. IEEE Int. Conf. Autom. Sci. Eng., 2016, pp. 626–632.], significant extensions are made in this letter by presenting new methods that lead to an overall improvement in the results. The robot system plans the actions of both the grasping and cleaning arms using its current model of the part deformation behavior, and attempts to minimize the overall cleaning time by finding plans that use a small number of grasping positions on the part. A finite-element method approach is used to model the part deformation and a general update algorithm is presented that can modify the stiffness parameters of the model to match observed deformation data collected during cleaning. This allows the system to very quickly discover the correct locations to grasp the part so as to minimize deformation. The methods described in this lettter are shown to achieve better results than the ones from our previous work: The results are much smoother, along with a twofold reduction in parameter-estimation error, and notable faster convergence.