Particle swarm optimization algorithm for path planning in robotic systems

RESUMEN: La planificación de trayectorias (path planning) dentro de un entorno físico o virtual a partir de un punto dado es un problema que juega un papel crucial en una gran variedad de campos. Uno de los más relevantes es la robótica, donde se utiliza para determinar las trayectorias a seguir por un robot o un conjunto de robots móviles moviendose a través de un entorno físico con obstáculos. En este TFG se aborda este problema desde el punto de vista de la inteligencia computacional, aplicando un algoritmo muy popular en este campo llamado optimización por sistemas de partículas (particle swarm optimization, PSO). El algoritmo considera un grupo de agentes, llamados partículas, que cooperan para determinar el valor óptimo del problema, expresado como un problema de optimización continuo. Mediante el uso de una función de fitness, que determina la calidad de cada solución considerada, el algoritmo computa la longitud de la distancia a recorrer para la trayectoria de cada agente. El algoritmo PSO explota la comunicación entre agentes para transmitir los mejores valores de dicha longitud a los miembros del grupo, así como el mejor histórico de los valores individuales de dicha función de fitness. El algoritmo procede de forma iterativa a lo largo de generaciones hasta determinar un valor óptimo para todo el grupo. El trabajo del TFG propuesto requiere la implementación del algoritmo en un entorno de programación o motor gráfico, la generación de un benchmark de escenarios gráficos 2D no triviales para probar el algoritmo (con obstaculos, topologías complicadas, etc.) y el análisis del rendimiento del algoritmo sobre dichos escenarios.ABSTRACT: Path planning within a physical or virtual environment from a given point is a problem that plays a crucial role in a wide variety of fields. One of the most relevant is robotics, where it is used to determine the trajectories to be followed by a robot or a set of moving robots moving through a physical environment with obstacles. This TFG addresses this problem from the point of view of computational intelligence, applying a very popular algorithm in this field called particle swarm optimization (PSO). The algorithm considers a group of agents, called particles, that cooperate to determine the optimal value of the problem, expressed as a problem of continuous optimization. Using a fitness function, which determines the quality of each solution under consideration, the algorithm computes the length of the distance to be covered for each agent's path. The PSO algorithm exploits communication between agents to transmit the best values of this length to the members of the group, as well as the best history of the individual values of this fitness function. The algorithm proceeds iteratively over generations to determine an optimal value for the entire group. The work of the proposed TFG requires the implementation of the algorithm in a graphical engine or programming environment, the generation of a benchmark of non-trivial 2D graphical scenarios to test the algorithm (with obstacles, complicated topologies, etc.) and the analysis of the algorithm's performance on those scenarios.Grado en Ingeniería Informátic