An information processing device adapted to search for one or more routes, the device comprising: a space constituting unit configured to arrange a scheduled traveling route and an obstacle in a search space represented by a coordinate space along a traveling possible region of a vehicle moving on the scheduled traveling route and a scheduled passing time axis or a scheduled passing speed axis orthogonal to the coordinate space, wherein the scheduled traveling route is a route over which the vehicle is scheduled to pass when the vehicle moves from a present location to a destination; a first arrangement unit configured to arrange one or more first nodes that are each a point used for searching for the one or more routes, in a first region on the scheduled travelling route, wherein the first region is a region other than an interference region, and wherein the interference region is a region overlapping with the obstacle on the scheduled traveling route; a second arrangement unit configured to arrange one or more second nodes that are each a point used for searching for the one or more routes, in a second region around the interference region, the second region deviating from the scheduled traveling route in the search space; wherein the second arrangement unit arranges the second nodes in the second region in the search space with a higher density than in the first region, and wherein the second arrangement unit arranges one or more second nodes in a third region deviating from the scheduled traveling route in at least one of a space before a scheduled passing time at which the scheduled traveling route overlaps with the obstacle or a scheduled passing speed at a position where the scheduled traveling route overlaps with the obstacle, and a space after the scheduled passing time at which the scheduled traveling route overlaps with the obstacle or the scheduled passing speed at a position where the scheduled traveling route overlaps with the obstacle, in the search space, and the second arrangement unit arranges the second node in the third region around at least one of an acceleration or deceleration start scheduled space in which the vehicle traveling on the scheduled traveling route starts acceleration or deceleration before overlapping with the obstacle and a deviation start scheduled space in which deviation from the scheduled traveling route is started to avoid the obstacle; a search unit configured to search for the one or more routes going through a plurality of nodes including a plurality of the first nodes and at least one of the second nodes and having a moving cost from a first point to a second point on the scheduled traveling route equal to or smaller than a threshold. a space constituting unit configured to arrange a scheduled traveling route and an obstacle in a search space represented by a coordinate space along a traveling possible region of a vehicle moving on the scheduled traveling route and a scheduled passing time axis or a scheduled passing speed axis orthogonal to the coordinate space, wherein the scheduled traveling route is a route over which the vehicle is scheduled to pass when the vehicle moves from a present location to a destination; a first arrangement unit configured to arrange one or more first nodes that are each a point used for searching for the one or more routes, in a first region on the scheduled travelling route, wherein the first region is a region other than an interference region, and wherein the interference region is a region overlapping with the obstacle on the scheduled traveling route; a second arrangement unit configured to arrange one or more second nodes that are each a point used for searching for the one or more routes, in a second region around the interference region, the second region deviating from the scheduled traveling route in the search space; wherein the second arrangement unit arranges the second nodes in the second region in the search space with a higher density than in the first region, and wherein the second arrangement unit arranges one or more second nodes in a third region deviating from the scheduled traveling route in at least one of a space before a scheduled passing time at which the scheduled traveling route overlaps with the obstacle or a scheduled passing speed at a position where the scheduled traveling route overlaps with the obstacle, and a space after the scheduled passing time at which the scheduled traveling route overlaps with the obstacle or the scheduled passing speed at a position where the scheduled traveling route overlaps with the obstacle, in the search space, and the second arrangement unit arranges the second node in the third region around at least one of an acceleration or deceleration start scheduled space in which the vehicle traveling on the scheduled traveling route starts acceleration or deceleration before overlapping with the obstacle and a deviation start scheduled space in which deviation from the scheduled traveling route is started to avoid the obstacle; a search unit configured to search for the one or more routes going through a plurality of nodes including a plurality of the first nodes and at least one of the second nodes and having a moving cost from a first point to a second point on the scheduled traveling route equal to or smaller than a threshold.