Final Project: AI

Práctica final: IA

Created by Álvaro Galisteo and Javier Fernández, this is the final project for the subject of artificial intelligence 2018/19 at Universidad Carlos III de Madrid.

Creada por Álvaro Galisteo y Javier Fernández, esta es la práctica final para la asignatura de artificial intelligence en la Universidad Carlos III de Madrid, curso 2018/19.

Technical document (in spanish)Memoria (en español)
GitHub

The project consisted in route finding in a logistical problem. Specifically, this is a problem in which a pizza delivery boy must deliver all the orders from different stores to different customers. Several improvements were also implemented to the logistics problem, such as different types of terrain and the use of electric motorcycles.

La práctica consistió en una búsqueda de rutas en problemas de logística. En específico, se trata de un problema en el que un repartidor de pizza debe entregar todos los pedidos de distintas tiendas a distintos clientes. Se implementaron además varias mejoras en el problema de logística tales como terrenos de distinta dificultad o el uso de motocicleta eléctrica.

Design

Diseño

The project makes use of different types of search algorithms, specifically, depth search, breadth search, Greedy and A*. Together with them, 11 different heuristic functions were developed, which were designed on the basis of asking the following question to different people:
If you were a pizza delivery man, which houses would you go to first?

La práctica hace uso de distintos tipos de algoritmos de búsqueda, en específico, búsqueda en profundidad, búsqueda en amplitud, Greedy y A*. Junto a ellos, se desarrollaron 11 funciones heurísticas distintas, que se diseñaron en base a realizar la siguiente pregunta a distintas personas:
¿Sí fueses un repartidor de pizza, a que casas irías primero?

The aim of this project is to implement different algorithms to deal with static logistics problems and to analyse the results to observe the influence of the heuristic functions and the performance of the different algorithms.

El objetivo de este proyecto es implementar distintos algoritmos frente a problemas de logística estáticos y analizar los resultados para observar la influencia de las funciones heurísticas y el rendimiento de los distintos algoritmos.

Structure

Estructura

The project is split into two parts:

La práctica consiste en dos partes:

  1. Basic part: The problem is to deliver 1 to 3 pizzas to a single customer from a single pizza shop.
  2. Advanced part: The problem is to deliver orders from several customers from several pizza shops with only one delivery person. Each map has special characteristics such as different difficulty terrains and limited distance vehicles.
  1. Parte básica: El problema consiste en entregar de 1 a 3 pizzas a un único cliente desde una única pizzería.
  2. Parte avanzada: El problema consiste en entregar pedidos de varios clientes desde varias pizzerías con un único repartidor. Cada mapa tiene características especiales tales como terrenos de distinta dificultad así como vehículo de distancia limitada.

In addition, the problem is defined with maps, stored in text files where each character in this file corresponds to an element of the problem, such as land, shops, customers, etc. More information can be found in the project repository.

Además, el problema se define mediante mapas, almacenados en archivos de texto donde cada caracter de este archivo se corresponde a un elemento del problema, tales como terrenos, tiendas, clientes, etc. Más información se podrá encontrar en el repositorio del proyecto.