Sistema y Gestión de Telecomunicaciones

Optimizing Heuristic Search Algorithms using Neural Networks

Abstract

Amine Ouardi

At the opposite side of the uninformed search algorithms, performing a systematic search, heuristic search algorithms are based on multiple rules leading it to estimate, in a predictive way, the minimal cost of the path from the current state to the goal.

In this sense, A* algorithm is an example of heuristics-based algorithms that can guarantee to find a least-cost path to a goal state if this algorithm is using an “admissible heuristic”. A heuristic is said to be “admissible” if it never overestimates the real path cost from the current state to the goal. Furthermore, if the condition h(x) ≤ d(x, y) + h(y) is satisfied by the heuristic h (d denotes that edge length), for every edge (x,y), then h is called consistent. And with consistent heuristics, finding an optimal path without processing any node more than once is guaranteed.

The main idea consists on developing a Neural Network that can optimize those heuristics to further refine the A* algorithm results. Towards achieving that goal we must find the best synaptic coefficients, for that reason, a learning phase will be needed during which the network parameters are adjusted until the best admissible and consistent heuristic is obtained, dominating any other heuristic (h1 dominates h2 if for every node n (state), h1(n)>h2(n) ).

During this learning phase, and as inputs, the neural network will have some representative examples in the form of pairs of several problems and heuristics ({P1,h1};{P2,h2}...{Pn,hn}), to finally be able to calculate the best heuristic regardless of the inputs.