To move through the world, mobile robots typically use a receding-horizon\nstrategy, wherein they execute an old plan while computing a new plan to\nincorporate new sensor information. A plan should be dynamically feasible,\nmeaning it obeys constraints like the robot's dynamics and obstacle avoidance;\nit should have liveness, meaning the robot does not stop to plan so frequently\nthat it cannot accomplish tasks; and it should be optimal, meaning that the\nrobot tries to satisfy a user-specified cost function such as reaching a goal\nlocation as quickly as possible. Reachability-based Trajectory Design (RTD) is\na planning method that can generate provably dynamically-feasible plans.\nHowever, RTD solves a nonlinear polynmial optimization program at each planning\niteration, preventing optimality guarantees; furthermore, RTD can struggle with\nliveness because the robot must brake to a stop when the solver finds local\nminima or cannot find a feasible solution. This paper proposes RTD*, which\ncertifiably finds the globally optimal plan (if such a plan exists) at each\nplanning iteration. This method is enabled by a novel Parallelized Constrained\nBernstein Algorithm (PCBA), which is a branch-and-bound method for polynomial\noptimization. The contributions of this paper are: the implementation of PCBA;\nproofs of bounds on the time and memory usage of PCBA; a comparison of PCBA to\nstate of the art solvers; and the demonstration of PCBA/RTD* on a mobile robot.\nRTD* outperforms RTD in terms of optimality and liveness for real-time planning\nin a variety of environments with randomly-placed obstacles.\n