Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for determining a point cloud augmentation policy and training a machine learning model using the point cloud augmentation policy to perform a perception task such as object detection or classification task by processing point cloud data. In general, training a machine learning model using the determined point cloud augmentation policy enables the model to more effectively perform the perception task, i.e., by generating higher quality perception outputs. When deployed within an on-board system of a vehicle, the machine learning model can further enable the on-board system to generate better-informed planning decisions which in turn result in a safer journey, even when the vehicle is navigating through unconventional environments or inclement weathers such as rain or snow.