Title: Optimizing Heuristic Search Algorithms using Neural Networks

Abstract:

On the opposite side of the uninformed search algorithms, performing a systematic search, heuristic search algorithms are based on multiple rules leading them to estimate, in a predictive way, the minimal cost of the path from the current state to the goal. In this sense, the 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 his called consistent. And with consistent heuristics, finding an optimal path without processing any node more than once is guaranteed. The main idea consists of 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, and 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.

Biography:

Ouardi Amine, 28 years old, head of Architecture perimeter, ELIS project, Capgemini; Artificial Intelligence Ph.D. student at ENSET Mohammedia, working on optimizing heuristics search algorithms using Neural Networks. Had a Master's degree in Imaging and Business Intelligence, with a graduation project on the Internet Of Things, including QR codes and NFC technology. Got a fundamental license degree in Mathematics and Computer Science, with a final project related to Genetic Algorithms: studying optimal solutions for the Travelling Salesman Problem.