An aspect includes space partitioning for vehicle motion planning. A plurality of obstacle data is analyzed to determine a plurality of obstacle locations in a configuration space of a vehicle. A partitioning of the configuration space is performed to compute a skeletal partition representing a plurality of obstacle boundaries based on the obstacle locations. The skeletal partition is used to preferentially place a plurality of samples by a sampling-based motion planner. At least one obstacle-free path is output by the sampling-based motion planner based on the samples.