Problem definition

The primary objective of this simulation is to thoroughly analyze and compare different movement algorithms designed for a robotic vacuum cleaner.

The focus is to evaluate their effectiveness by focusing on key performance metrics, including cleaning speed, power consumption, and overall performance.

Method

The simulation will be developed using NetLogo, an agent-based modeling platform. NetLogo is ideal for simulating complex systems with numerous interacting agents (in case of this simulation - a robot vacuum and pieces of trash).

Room setup

The room and furniture was created using patches.

I originally wanted to make the furniture using agents as you can see in the assigment, however after using this method I realized that than making each furniture using agents is not an ideal solution. First of all, furniture is static and does not have to move around. Also, patches are easier to visualize using their color or shape because agents have a limited shape options.So this is why it was easier to arrange furniture as a set of patches.

The room itself was imagined as a living room with a coffee table in the middle and two sofas around it.

Trash placement

A procedure named setup-trash is designed to simulate the placement of trash in the environment. It creates 50 trash agents, represented by green "x" shapes, and attempts to place them on random white patches of the room that also do not already contain trash. If a suitable patch is found, the trash agent is positioned there, and the patch is marked as occupied; otherwise, the trash agent is removed. Then, the total number of successfully placed trash agents is counted and stored in the variable total-trash.

Vacuum setup

Setup-robot function creates a single robot agent. The robot is represented as a cyan-colored circle with a size of 2. It is initialized with an energy level of 0. The robot is placed on a randomly selected white patch that does not contain trash. The robot is also labeled with the text "Robot".

Energy

Energy is a parameter of a robot that starts with a 0 and acumulates a specific value over the course of the simulation. Different actions recuire different energy usage. For example, every step forward is considered to have a value of 1, every turn, because the brushes are used differently when turning, has a value of 0.5 and finally, the hardest action of all, trash collection, has a value of 2.

Model

Random Walk

The movement algorithm characterized as "random walk" implies that an object moves through space without a predetermined trajectory and/or target. In this case, the object moves in an arbitrary direction until it encounters an obstacle, such as a wall or a piece of furniture. Upon detecting an obstacle, the object selects a new random direction to continue its movement. And the cycle continues until all the trash is collected.

This approach does not involve any strategy or route optimization, which means the object may spend a significant amount of time moving within a limited space, constantly changing direction after each collision. This results in a "wandering" effect, where the object chaotically rebounds off walls without reaching a specific goal or destination.

The random walk algorithm, despite its' negative sides, is still widely used because it is one of the simplest algorithms that can be used in robot vacuum cleaners. Its main advantage is the simplicity of implementation. This approach does not require complex calculations, room mapping or expensive sensors, making it ideal for budget models.

The random walk algorithm has significant disadvantages that limit its effectiveness. Firstly, the robot can repeatedly clean the same areas while other areas remain untidy. This results in longer cleaning time and wasted energy. Secondly, in large rooms, the robot can wander around for hours without completing the task. Lastly, the algorithm does not take into account the structure of the room (e.g., walls or furniture) and does not optimize the route, making it less efficient than more advanced methods.

File:Kulv05 randomwalk algorithm.nlogo

Wall-to-wall

The "Wall-to-Wall" is an algorithm that involves the robot vacuum first finding a wall and then moving along it, cleaning the perimeter of the room. This approach is effective for removing debris in corners and along walls, where dirt often accumulates. However, if this algorithm is used in its original form or on its own, it is not optimal for a complete room cleaning. The main issue is that the robot ignores the central part of the room, where debris may also be present. As a result, even if the perimeter is perfectly clean, the center of the room remains uncleaned, significantly reducing the overall efficiency of the cleaning process. Thus, as you can see in a showcase of the simulation below, in its pure form, the "Wall-to-Wall" algorithm cannot be considered an optimal solution for thorough room cleaning. The trajectory was inspired by the "Improving robotic vacuum cleaners" article. [1]

The algorithm, due to its nature, constanly loops near the walls, so to analyze the effitiency I decided to stop after 1000 ticks and apply all the formulas to see the results. It does not finish after all the trash was collected, but after 1000 ticks have passed.

File:Kulv05 standart walltowall algorithm.nlogo

Wall-to-wall + Horizontal Zigzag

The "Wall-to-wall" algorithm enhanced by the Horizontal Zigzag algorithm is a combination of algorithms that help us reach the goal - collect all the trash in the room. The "Horizontal Zigzag" logic was specifically made as a support function for this project's not ideal trajectories that do not cover the whole room itself.

The robot starts moving forward the already discussed "Wall-to-wall" algorithm. The robot keeps track of how many room corners it has passed. After completing two full loops (8 corners) and then it switches to the next stage — Horizontal Zigzag.

At this stage, the robot moves in a zigzag pattern across the room. It starts moving either right or left until it reaches a wall or obstacle. When the robot reaches a wall, it moves up (or down) one row and changes direction. If the robot reaches the top boundary of the room, it switches to moving downward. If it reaches the bottom boundary, it switches to moving upward. It covers the patches that were not visited before, ensuring that the trash can be collected.

The algorithm ensures that the robot covers the entire room, including hard-to-reach areas like corners and the center. This is crucial for tasks like cleaning, where missing even a small area can be problematic. By combining wall-following and horizontal zigzag movements, the robot systematically explores the space, minimizing the chances of leaving any trash behind.

File:Kulv05 walltowall horiz zigzag algorithm.nlogo

Spiral

Идет спиралью до того как доходит до стен комнаты. When the front bumper is triggered the robot cleaner stops the spiral algorithm and proceeds with another algorithm since starting the spiral algorithm when close to a wall is meaningless. (источник) Я решила попробовать сделать другим алгоритмом спираль, однако в обратную сторону. Обратная спираль, хотя и выглядит логически последовательной, на практике часто оказывается менее эффективной, особенно в случаях, когда робот начинает повторно покрывать области, которые уже очищены. Этот алгоритм может быть полезен в некоторых специфических условиях, но на моем реальном примере показало худший результат чем random-walk. Что говорит о том, что в реальных задачах он может уступать другим стратегиям.

A spiral trajectory works great in a lot of free space, however the room filled with a lot of furniture is not the best option.

The trajectory was inspired by the "Improving robotic vacuum cleaners" article. [1] An "A performance comparison of coverage algorithms for simple robotic vacuum cleaners" article mentioned, that the spiral algorithm is no longer a good option as it becomes a sort of "wall-to-wall" algorithm and inherits all the negatives of it, and the article adviced to combine it with another algorithm which you will be able to see it the next showcase of an algorithm. [4]

Zigzag

The algorithm, using the trajectory inspired by the "Improving robotic vacuum cleaners" article [1], due to its nature, constanly loops near the left, so to analyze the effitiency I decided to stop after 1000 ticks and apply all the formulas to see the results. It does not finish after all the trash was collected, but after 1000 ticks have passed.

File:Kulv05 standart zigzag algorithm.nlogo ‎

Combined Zigzags

SLAM (simultaneous localization and mapping)

[2]

A*

A robot vacuum cleaner using the A* algorithm, unlike the other examplex, does not follow a predetermined trajectory. Instead, it employs an intelligent A*-based planner that helps calculate the shortest path from the robot's current position to the nearest trash agent, while taking into account obstacles such as walls or furniture. [3] The planner analyzes possible paths from the robot's current location to the target, compares them, and selects the fastest and most efficient route. The robot is then provided with a list of cells to follow to reach the goal. The robot moves along the proposed route, collects the debris, and then repeats the process to search for the next target. This approach makes cleaning more systematic and efficient.

The algorithm works by combining two main elements: the actual cost of the path the robot has already traveled and the estimated (heuristic) cost of the remaining distance to the target. This helps the robot make smart decisions about which direction to move in. I used a heuristic function, such as the Manhattan distance, to estimate how far the robot is from the goal. The Manhattan distance is simple yet effective — it adds up the horizontal and vertical distances between the robot and the target. Based on that, the algorithm always chooses the path with the lowest total cost, which means the robot avoids unnecessary movements and saves time. It is important to mention that the A* algorithm considers obstacles like walls or furniture and excludes them from possible routes. This allows the robot to find the best way around obstacles and clean efficiently, even in complex rooms.

I want to mention that it took a lot of time and countless tries to create a algorithm as complex as A* in NetLogo, I tried a few of different approaches, one of them was to work with the Netlogo py extention (it allows to run the Python code in NetLogo). But the thing that helped me the most was the "A General A∗ Solver in NetLogo" article [5]. It greatly helped me to understand the logic behind the implementation of algorithm in NetLogo.

File:Kulv05 astar algorithm.nlogo

Results

Random Walk Results

Wall-to-wall Results

Wall-to-wall + Horizontal Zigzag Results

Zigzag Results

A surprising revelation was to see the algorithm collect the most part ot the trash during the trajectory run. Unlike the Wall to wall standart trajectory, the zigzag one turned out to be a good competitor. Although it still misses trash particles, it is able to go through the wast majority of the map and collect trash there (if the random placement if good enough) in 1000 ticks, something that a few other trajectories are unable to accomplish.

If we look at the definition that the robotic vacuum cleaners' algorithms do not guarantee that all room will be cleaned at the end of the cleaning, nor do they guarantee that there will be no untidy areas left within a single room, this algorithm seems to be a great option.