本发明实施例提供了一种自动驾驶速度的规划方法及装置、车辆和存储介质，方法包括：在目标车辆基于目标路径进行自动驾驶的过程中，将目标路径上目标车辆未经过的一位置作为第一位置，以及将目标车辆当前的位置作为第二位置；将第一位置的状态信息作为父节点，并根据父节点和预先离散采样得到的加加速度集合，确定父节点对应的至少一个子节点；子节点包括相对于父节点对应位置预设时长间隔的下一位置的状态信息；将至少一个子节点添加至开列表中，并将至少一个子节点中成本值最小的子节点移动至闭列表中；根据闭列表中的子节点，确定用于自动驾驶的目标速度曲线。通过本发明实施例，实现了基于对加加速度的离散采样来进行准确的速度规划。