Algoritmo de guiado a zonas de aparcamiento definidas por el usuario en un sistema de Valet Parking autónomo

Rodríguez de Rivas Moreno, Álvaro (2022). Algoritmo de guiado a zonas de aparcamiento definidas por el usuario en un sistema de Valet Parking autónomo. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. Industriales (UPM).

Description

Title: Algoritmo de guiado a zonas de aparcamiento definidas por el usuario en un sistema de Valet Parking autónomo
Author/s:
  • Rodríguez de Rivas Moreno, Álvaro
Contributor/s:
  • Jiménez Alonso, Felipe
Item Type: Final Project
Degree: Grado en Ingeniería en Tecnologías Industriales
Date: June 2022
Subjects:
Freetext Keywords: Sistema Valet Parking Autónomo, conducción autónoma, exploración de rutas, optimización
Faculty: E.T.S.I. Industriales (UPM)
Department: Ingeniería Mecánica
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB)

Abstract

Los vehículos autónomos son una tecnología que está cobrando una gran importancia con un futuro muy prometedor. Los avances tecnológicos, junto con la popularización de los coches eléctricos y la creciente aceptación social están haciendo de este campo uno de los más llamativos y rápidamente crecientes. Una aplicación de especial utilidad de esta tecnología son los sistemas de Valet Parking Autónomos. Estos permiten a los conductores depositar su coche a la entrada de un aparcamiento y que éste, de manera autónoma, busque una plaza libre y aparque, ahorrando de esta manera el tiempo y esfuerzo que habrían sido necesarios para hacer esa tarea de forma manual. Este trabajo se desarrolla en el contexto de una aplicación que implementa esta idea aplicándola a aparcamientos exteriores. Dado que estos no suelen contar con infraestructura para determinar las plazas libres, surge la necesidad de seguir una ruta a través del parking en busca de un lugar donde aparcar. En la aplicación mencionada se desarrollan todas las etapas del proceso de automatización, a excepción esta última. Este es el problema abordado en el presente proyecto. Para resolver el problema anterior se ha planteado una simplificación del plano de un parking expresándolo en una cuadrícula. Dado un plano de este tipo, el problema resuelto es desarrollar un algoritmo capaz de hallar la ruta de menor longitud que visite las plazas de aparcamiento seleccionadas en busca de una libre. Este problema se ha planteado como un problema de grafos y se ha reducido a otro más sencillo equivalente para ser posteriormente resuelto. Además, se ha creado una aplicación para poder realizar pruebas sobre este algoritmo. Ésta permite introducir un plano de forma sencilla y muestra la ruta decidida de manera clara al usuario. Utilizando esta aplicación el algoritmo ha sido comprobado en una variedad de ejemplos de parking ficticios y en uno real, dando resultados correctos en un tiempo razonable. Finalmente, se ha realizado un análisis del tiempo de ejecución del algoritmo en distintos casos. A la vista de estos datos se ha realizado un modelo de regresión exponencial para aproximar el tiempo de cálculo en función del número de nodos y aristas del grafo sobre el que se aplica el algoritmo. Esta aproximación es capaz de predecir el orden de magnitud del tiempo necesario. Además, se ha concluido que la complejidad de tiempo del algoritmo se puede considerar 0(e"+^) donde JV es el número de nodos y ^ el de aristas. ----------- ABSTRACT ------------- The field of autonomous vehicles is one which is taking a great significance and has a very promising future. Technological advances as well as the popularization of electric cars and an increasing social acceptance are making this field one of the most noteworthy and quickly growing. An especially useful application of this technology is Autonomous Valet Parking Systems. These systems allow drivers to leave their car at the entrance of a parking lot, and it will, in a fully autonomous way, search for a free parking space and park in it, sparing the time and effort that would have been invested in doing the task manually. This work takes place in the context of an application of this technology which implements this idea for outside parking lots. These usually lack the infrastructure to determine which parking spaces are free, so the need arises to follow a route through the parking lot in search of a free space to park the car in. In the aforementioned application all phases of the automation process are developed, with the exception of the definition of this route. This is the problem tackled is this project. To solve this problem, a simplification of the layout of the parking lot has been made, fitting it onto a square grid. Given a grid representing the blueprint for a parking lot, the problem solved is to find the path of shortest length which visits the parking spaces selected by the user in search of a free one. This problem has been expressed as a graph problem and reduced to an equivalent but simpler one to be solved. Furthermore, an app has been developed to test the algorithm. This app allows the user to input a parking layout into the grid in an easy way, and shows the path chosen in a clear and easily digestible way. Using this app, the algorithm has been tested in a variety of fictional parking lot examples, as well as in a real one, providing correct results in a reasonable amount of time. Finally, an analysis of the execution time has been made, testing the algorithm for different cases. With these results, an exponential regression model has been made to approximate the execution time as a function of the number of nodes and edges of the input graph. The approximation found can correctly predict the order of magnitude of the time needed. Furthermore, it’s been concluded that the time complexity of the algorithm can be considered 0(e"+*) where JV and E are the number of nodes and edges, respectively.

More information

Item ID: 70775
DC Identifier: https://oa.upm.es/70775/
OAI Identifier: oai:oa.upm.es:70775
Deposited by: Biblioteca ETSI Industriales
Deposited on: 14 Jul 2022 13:11
Last Modified: 15 Sep 2022 22:30
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM