Algorithme A* | EPFL Graph Search

En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle. L'algorithme A* a été créé pour que la première solution trouvée soit l'une des meilleures, c'est pourquoi il est célèbre dans des applications comme les jeux vidéo privilégiant la vitesse de calcul sur l'exactitude des résultats. Cet algorithme a été proposé pour la première fois par Peter E. Hart, Nils John Nilsson et Bertram Raphael en 1968. Il s'agit d'une extension de l'algorithme de Dijkstra de 1959 (p. 30-31 dans ). Histoire vignette|L'algorithme A* a été inventé par des chercheurs qui travaillaient sur la planification du robot Shakey. En 1968, le chercheur en intelligence

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has become extremely costly and inefficient, which motivates the study of sublinear algorithms. This thesis focuses on studying two fundamental graph problems in the sublinear regime. Furthermore, it presents a fast kernel density estimation algorithm and data structure. The first part of this thesis focuses on graph spectral sparsification in dynamic streams. Our algorithm achieves almost optimal runtime and space simultaneously in a single pass. Our method is based on a novel bucketing scheme that enables us to recover high effective resistance edges faster. This contribution presents a novel approach to the effective resistance embedding of the graph, using locality-sensitive hash functions, with possible further future applications.The second part of this thesis presents spanner construction results in the dynamic streams and the simultaneous communication models. First, we show how one can construct a

\tilde{O}(n^{2/3})

-spanner using the above-mentioned almost-optimal single-pass spectral sparsifier, resulting in the first single-pass algorithm for non-trivial spanner construction in the literature. Then, we generalize this result to constructing

\tilde{O}(n^{2/3(1-\alpha)})

-spanners using

\tilde{O}(n^{1+\alpha})

space for any

\alpha \in [0,1]

, providing a smooth trade-off between distortion and memory complexity. Moreover, we study the simultaneous communication model and propose a novel protocol with low per player information. Also, we show how one can leverage more rounds of communication in this setting to achieve better distortion guarantees. Finally, in the third part of this thesis, we study the kernel density estimation problem. In this problem, given a kernel function, an input dataset imposes a kernel density on the space. The goal is to design fast and memory-efficient data structures that can output approximations to the kernel density at queried points. This thesis presents a data structure based on the classical near neighbor search and locality-sensitive hashing techniques that improves or matches the query time and space complexity for radial kernels considered in the literature. The approach is based on an implementation of (approximate) importance sampling for each distance range and then using near neighbor search algorithms to recover points from these distance ranges. Later, we show how to improve the runtime, using recent advances in the data-dependent near neighbor search data structures, for a class of radial kernels that includes the Gaussian kernel.

EPFL2022

Accelerated SGD for Non-Strongly-Convex Least Squares

Nicolas Henri Bernard Flammarion, Aditya Vardhan Varre

We consider stochastic approximation for the least squares regression problem in the non-strongly convex setting. We present the first practical algorithm that achieves the optimal prediction error rates in terms of dependence on the noise of the problem, as

O(d/t)

while accelerating the forgetting of the initial conditions to

O(d/t^2)

. Our new algorithm is based on a simple modification of the accelerated gradient descent. We provide convergence results for both the averaged and the last iterate of the algorithm. In order to describe the tightness of these new bounds, we present a matching lower bound in the noiseless setting and thus show the optimality of our algorithm.

2022

Real Time Emotional Control for Anti-Swing and Positioning Control of SIMO Overhead Traveling Crane

Arash Arami, Babak Hosseini

Research in artificial intelligence and bioinspired algorithms is still being actively pursued in different fields of engineering. In this work, Brain Emotional Learning Based Intelligent Controller (BELBIC) is applied for real time positioning of laboratorial overhead traveling crane. This controller is based on biologically motivated algorithm originating from emotional processes in the limbic system of the mammalian brain. Simulations show that learning capability, adaptation, robustness and other control concerns of this controller are comparable with conventional techniques and lead to better performance in many cases. Two objectives, tracking desired position and keeping pendulum vertically, must be considered simultaneously. A bottom up strategy was utilized for designing the controllers. First separated BELBICs were designed for each control task. Next, in order to compensate the actual coupling between control tasks, the objective of each control tasks was considered in the stress signal of the other one. Obtained results in real tracking applications are also comparable with other conventional and intelligent approaches such as hierarchical fuzzy control (HFLC) and confirm the simulation results. Learning capability, model free control algorithm, robustness and fast response are main characteristics of this controller and designer can define emotional stress signal based on control application objectives.

2008