VEHICLE CONTROL DEVICE, VEHICLE CONTROL METHOD, AND STORAGE MEDIUM

A vehicle control device includes a recognizer configured to recognize a surrounding environment of a vehicle and a driving controller configured to perform driving control according to speed control and steering control of the vehicle on the basis of a recognition result of the recognizer. The recognizer includes a physical object recognizer configured to recognize a physical object present on a route of the vehicle on the basis of an image acquired from an imaging unit configured to image a space in a traveling direction of the vehicle and an obstacle determiner configured to determine whether or not the physical object recognized by the physical object recognizer is a specific obstacle that hinders traveling in a lane where the vehicle is currently traveling. The driving controller is configured to start a lane change execution possibility determination before the obstacle determiner makes the determination or simultaneously with a start of the determination in a case where the physical object recognizer has recognized the physical object and the vehicle is allowed to make the lane change.