A navigation system is provided which dynamically changes a destination so as to meet a user's objective, based on various changes in situation which occur during traveling, and indicates a changed destination to the user. An objective representing an action of a user is recognized based on information inputted by the user (S201). A place at which the recognized objective can be achieved is set as a destination (S203). Guidance is performed so as to reach the destination having been set (S204). When it is determined, during traveling based on the guidance, that the objective is difficult to achieve, a substitute place at which the objective can be achieved is set as a destination (S206 to S209).