A robot may identify a human located proximate to the robot in a physical environment based on sensor data captured from one or more sensors on the robot. A trajectory of the human through space may be predicted. When the predicted trajectory of the human intersects with a current path of the robot, an updated path to a destination location in the environment may be determined so as to avoid a collision between the robot and the human along the predicted trajectory. The robot may then move along the determined path.