This paper presents an algorithm for unknown environment exploration based on the local navigation algorithm (LNA). The original LNA doesn’t take into account the case in which the robots are trapped and stop exploring the environment. In this paper, we propose some modifications to overcome this problem and demonstrate it by using real robots. For validation purpose, we ran several experiments using the mini-robot Khepera II running on the Teleworkbench. The complete environment is divided into small quadratic patches with some objects placed in it representing obstacles. With on-board infrared sensors and wheel encoder, the robot can successfully explore the unknown environment. Moreover, by calculating the distance to surrounding patches, the implemented algorithm will minimize the distance traveled, and in turn of the consumed energy and time. This paper also shows the advantage of using the Teleworkbench for performing experiments using real robots.