A moving robot includes: a sensor to acquire terrain information; a memory to store node data for at least one node; and a controller, and the controller determines whether at least one open movement direction exists among a plurality of movement directions, based on sensing data and the node data, generates a new node in the node data when at least one open movement direction exists, determines any one of the open movement directions as a traveling direction for the robot, determines whether at least one of the nodes needs to be updated exists, based on the node data when the open movement direction does not exist, controls the moving robot to move to one of the nodes that need to be updated, and generates of a map including the at least one node, based on the node data, when the node that needs to be updated does not exist.