Object-search robot

Autonomous mobile robots can choose independently which actions to perform. This project sought to develop an object-search robot using the LEGO Mindstorms Education EV3 kit, with emphasis on the robot accurately knowing its position within the map at all times. An occupancy grid map representing the environment in which the robot is placed was constructed, on which an object was randomly positioned within the environment. The robot was set to determine its position within the map using Monte Carlo localization (MCL), navigating the environment to locate the object and, upon doing so, would note the exact location of the object. The robot used the A* path-planning algorithm to plan the shortest path to reach the object, and a PID controller to control the robot’s motors in order to move it towards the object.

MCL is an algorithm that enables the robot to figure out, and keep track of, its position within the map. This uses a number of weighted particles in order to represent its belief of where the robot may be located within the environment. An accurate model of how the robot should move (motion model) was implemented, such that each particle could mimic the real robot’s position. Similarly, a model was developed for the sensor so that each particle could simulate a sensor reading from the robot. A process of resampling was then performed. In this process, particles of a certain weight that indicated being closer to the robot’s actual position were chosen again, whereas the lighter particles would be killed off. Figure 1 shows the process of localization over time.

The robot was equipped with two ultrasonic sensors, one at the front and another at the side. These sensors helped gather information that was subsequently used to determine the location of both robot and object within the environment.

The algorithm’s performance was tested in a room with smooth floors and wooden furniture, without obstacles. When testing with a small number of particles, the algorithm converged towards the wrong position. This premature convergence was counteracted by increasing the number of particles, which led to accurate localization within 10cm when 300 particles were used. However, this was achieved at the cost of time, as it increased computation time. Erroneous readings from the sensors could be considered to be the main cause of performance decrease when testing the system.

Figure 1: Over time, the particles converge to one spot, which corresponds to the robot’s actual position [1]


[1] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics (Intelligent Robotics and Autonomous Agents). The MIT Press, 2005.

Student: Jeremy Busuttil
Course: B.Sc. IT (Hons.) Artificial Intelligence
Supervisor: Dr Ingrid Vella