Robots for minimally-invasive surgery such as steerable needles and concentric-tube robots have the potential to dramatically alter the way common medical procedures are performed. They can decrease patient-recovery time, speed healing and reduce scarring. However, manually controlling such devices is highly un-intuitive and automatic planning methods are in need. For the automation of such medical procedures to be clinically accepted, it is critical from a patient care, safety, and regulatory perspective to certify the correctness and effectiveness of the motion-planning algorithms involved in procedure automation. In this paper, I survey recent and ongoing work where we develop efficient and effective planning capabilities for medical robots that provide provable guarantees on various planner attributes as well as introduce new and exciting research opportunities in the field.