A trajectory generation device which generates a trajectory of a robot includes: a trajectory exploration graph generation unit which is configured to generate a trajectory exploration graph composed of a plurality of nodes for generating the trajectory; an acceleration upper limit value acquisition unit which is configured to acquire a first acceleration upper limit value based on orientations and an acceleration direction of the robot at a current node; a velocity and acceleration setting unit which is configured to set a first velocity representing a velocity when moving from the current node to a next node adjacent to the current node based on the acquired first acceleration upper limit value, and an acceleration; and a node cost calculation unit which is configured to calculate a moving time by using the set first velocity and the acceleration as cost from the current node to the next node.