A trajectory planning system obtains a trajectory for controlling a state of an object toward a goal state. The system includes a search tree generating section which registers a state of the object as a root of a search tree in a state space, registers a next state of the object after a lapse of a predetermined time interval obtained through dynamical relationships during the time interval as a branch of the search tree in the state space. The system further includes a known-state registration tree storing section which stores a known-state registration tree and a known-state registration tree generating section which determines a cell to which the next state belongs among a plurality of cells previously prepared by segmenting the state space, determines whether or not a state which belongs to the cell has already been registered as a branch of the known-state registration tree, discards the next state when a state which belongs to the cell has been registered, and registers the next step as a branch of the known-state registration tree when a state which belongs to the cell has not been registered. The system further includes a trajectory generating section which selects a state whose distance to the goal state is minimum among states registered as branches of the known-state registration tree and obtains a trajectory using a sequence of states in a backward direction from the state toward the root of the known-state registration tree.