logo

AI Search Algorithms for Smart Mobility

  • AI Search Algorithms for Smart Mobility
  • Getting Started
  • Introduction to Geospatial Data Science
    • Spatial Data and Geographic Information System (GIS)
    • Projection
    • Visualization
  • Graph Search Algorithms
    • From Road Network to Graph
    • Graph Search
    • Blind Search Algorithms
    • Informed Search Algorithms
    • Search Algorithm Comparison
  • Trajectory-based Algorithms
    • Tabu Search
    • Simulated Annealing
  • Evolutionary Computing Algorithms
    • Generating Initial Populations
    • Genetic Algorithms
  • Swarm Intelligence Algorithms
    • Particle Swarm Optimization
    • Ant Colony Optimization
    • Artificial Bee Colony
    • Firefly Algorithm
  • Learn to Search
    • Geometric Deep Learning
    • Graph Neural Networks (GNN)
    • Attention Mechanisms
    • Reinforcement Learning
  • People Mobility Problems
    • Car-Sharing Service
    • Trip Itinerary Planning
    • Multi-Criteria Routing
    • Deadheading in Ride-Hailing
  • Logistics Problems
    • Delivery Vehicle Routing
    • Eco-efficient Delivery
  • Infrastructure Problems
    • Emergency Dispatch and Routing
  • Tools and Python Libraries
  • Datasets
  • References
Powered by Jupyter Book

Learn to Search¶

Machine learning (ML) is a subfield of AI that endows an artificial system/process with the ability to learn from experience and from observation without being explicitly programmed. ML algorithms are traditionally categorized into supervised, unsupervised, and reinforcement learning algorithms. First, supervised learning uses inductive inference to approximate mapping functions between data and labels/classes. This mapping is learned using already labeled training data. Second, unsupervised learning deals with unlabeled data through techniques like clustering and data association. The third category of ML algorithms is reinforcement learning (RL), which is a weakly supervised learning technique that learns from interactions through a feedback loop or by trial and error. RL learns what to do (i.e., how to map a situation to actions) to maximize a numerical reward function. As illustrated in the figure below, Deep learning (DL) is a subfield of machine learning concerned with learning of underlying features in data using deep neural networks enabling artificial systems to learn at different levels of abstractions and to build complex concepts out of simpler concepts.

ML techniques can be used to search space and to solve combinatorial optimization problems on graphs using end to end learning approaches (whether from imitation/demonstration or experience). ML techniques can also be combined with metaheuristics search techniques to form multi-stage/sequential or parallel hybrid metaheuristics. For example, deep learning assisted heuristic tree search (DLTS) consists of a heuristic tree search in which decisions about which branches to explore and how to bound nodes are made by deep neural networks (DNNs) [10]. ML techniques can be applied to configure or auto-tune the parameters of the search algorithms. Examples include, but are not limited to, learning rate/step size in gradient descent methods; finding initial temperature or cooling schedule of simulated annealing, standard deviation of Gaussian mutation or selective crossover of genetic algorithm, inertia weight or cognitive and social acceleration coefficients of PSO or to tune the rate of evaporation, influence of pheromone deposited or influence of desirability of state transition in ACO. We will focus here on the end-to-end learning for solving combinatorial optimization problems. The end-to-end pipeline for combinatorial optimization or operation research problems are shown in the following figure.

Through graph embedding, we can adapt existing machine learning technologies to directly process non-Euclidean structured data as input, so that this (possibly useful) information is not lost in transforming the data into a Euclidean input as required by existing techniques. The following topics are covered:

  • Geometric Deep Learning

  • Graph Neural Networks (GNNs)

  • Attention Mechanisms

  • (Deep) Reinforcement Learning

Firefly Algorithm Geometric Deep Learning

By Alaa Khamis and Yinan Wang
© Copyright 2021, Alaa Khamis and Yinan Wang.