|In this work, we propose an algorithm that can plan safe and efficient robot trajectories in real time, given time-parameterized motion predictions, in order to avoid fast-moving obstacles in human-robot collaborative environments. Our algorithm is able to reduce the robot configuration space and the time domain significantly by constructing a Lazy Safe Interval Probabilistic Roadmap based on a pre-planned path. The algorithm then plans efficient obstacle-avoidance strategies within the space-time roadmap. We benchmarked our algorithm by evaluating the performance of a simulated 6-joint manipulator attempting to avoid a quickly moving human hand, using a dataset collected from human experiments. We compared our algorithm’s performance with those of 8 variations of prior state-of-the-art planners. Results from this empirical evaluation indicate that our method generated safe plans in 97.5% of the evaluated situations, achieved a planning speed 30 times faster than the benchmarked methods that planned in the time domain without space reduction, and accomplished the minimal solution execution time among the benchmarked planners with a similar planning speed.