A control device mounted on a mobile object acquires surrounding situation information indicating a surrounding situation of a mobile object recognized by an object recognition device mounted on the mobile object, detects a predetermined reference object present in a traveling direction of the mobile object on the basis of the surrounding situation information, identifies a travelable area of the mobile object on the basis of the surrounding situation information, controls traveling of the mobile object such that the mobile object travels in the travelable area, causes the mobile object to move closer to the reference object when the reference object is detected, and detects an accompanying object accompanying the reference object on the basis of the surrounding situation information recognized by the object recognition device after the mobile object moves closer to the reference object, and identifying the travelable area by excluding the reference object and the accompanying object.