Robotic Vacuum Algorithms Simulation (kulv05)
Contents
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".
Model
Для этой симуляции мною было использовано agent-model based simulation with the help of the NetLogo software. Для каждой алгоритма был создан свой малый метод. Для сбора мусора был создан метод collect-trash. Спаунится мусор Комната и мебель была создана с помощью патчей. Изначально я хотела сделать их с помощью агентов, однако после применения этого способа поняла, что чем делать каждую мебель агентами. Это было легче устроить из-за
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.
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.
Wall-to-wall + Horizontal Zigzag
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. Что говорит о том, что в реальных задачах он может уступать другим стратегиям.
Zigzag
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. 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. It greatly helped me to understand the logic behind the implementation of algorithm in NetLogo.
Results
Conclusion
Citations
https://www.diva-portal.org/smash/get/diva2:1213349/FULLTEXT02.pdf https://ouster.com/insights/blog/introduction-to-slam-simultaneous-localization-and-mapping https://www.geeksforgeeks.org/a-search-algorithm/ https://www.diva-portal.org/smash/get/diva2:1213970/FULLTEXT02.pdf https://www.cs.us.es/~fsancho/Blog/posts/General_A_Solver_NetLogo.md.html#a*forpathfindingin2dgrids
