The present disclosure relates to a control device, and a control method, a program, and a mobile body that enable efficient search for surrounding information when it is in an own position indefinite state. When it is in an own position indefinite state, on the basis of an own position, obstacle position information around oneself, and information of a surface sensing possible range of a surface sensing unit including a stereo camera for determining the own position, information of a surface-sensed area of an obstacle is recorded, and a search route is planned on the basis of the information of the surface-sensed area of the obstacle. The present technology can be applied to a multi-legged robot, a flying body, and an in-vehicle system that autonomously move according to a mounted computer.