I do not think this is too ambitious and the Arduino should manage the logic nicely. Just Google: video automatic cat box and watch a few of the ways the commercial units work. Then replicate, reengineering the bagging cycle to use old grocery bags.
I'm not sure the cats would be too amused at a vacuum cleaner coming from a hidden compartment to clean the out-of-box spillage, however 