Motion planning remains a fundamental problem in robotics. Sampling-based algorithms use randomization to allow efficient solutions to this complex problem. As mobile robots and autonomous vehicles become more prevalent in everyday life, motion planning must be applied to increasingly challenging scenarios. Safety has become a paramount concern in motion planning for ensuring robotic applications enrich human lives. To date, many motion planning techniques to increase safety in the face of uncertain and dynamic environments have been developed. This dissertation first addresses distributional safety of Rapidly-Exploring Random Trees (RRT) through our algorithm W-Safe RRT. To acknowledge distributional uncertainty and poor modeling, W-Safe RRT uses the Wasserstein metric to provide a probabilistic bound on the distributional distance between a robot and obstacles. Discerning between environmental actor behaviors in a human-understandable way can allow online safety margin adaptation. We address the use of an integrating-region method for online classification in order to correctly label actors based on behavioral feature values. The method performs class assignments based on \textit{local} maximum likelihood in a created behavioral feature-space, allowing a notion of classification uncertainty. Model-based methods with safety guarantees can quickly become computationally intractable, especially with multiple agents, higher dimensions, and plentiful unknowns. Sampling-based algorithms have been parallelized for computation with multi-core computers and GPUs. We consider the use of quantum algorithms and computers, which can be thought of as fully parallelized, for sampling-based motion planning for the first time. With Quantum-RRT, we recast the motion planning problem into a database-search structure and use Quantum Amplitude Amplification to find reachable states in the database with a quadratic performance increase over classical methods. We address two error sources with this method: quantum measurement and quantum oracle errors. We then extend this method to Parallel Quantum-RRT, which uses a manager-worker architecture with multiple parallel quantum workers to increase database search efficiency. We characterize probabilities of multiple workers finding solutions and test, in simulation, the quantum algorithms against classical versions in a variety of scenarios.