Algoritmos de pesquisa por caminhos são estudados desde a antiguidade, mas desenvolveram-se formalmente sobre o modelo de matemático de Grafo principalmente no século passado. O algoritmo de Dijkstra apresentado em 1959 faz uma pesquisa BFS à partir da origem até encontrar o destino. Em 1968 Hart, Nilsson e Raphael apresentaram o algoritmo A*, que usa informações da estrutura do grafo para saber quais são os nodos mais promissores a pesquisar. A* inaugurou a "pesquisa heurística", mas ainda assim é capaz de encontrar o caminho ótimo. Também foi provado que ele é extremamente eficiente, e sob algumas condições é um algoritmo ótimo, ou seja, não é possível existir outro algoritmo de pesquisa unidirecional que seja mais eficiente. A pesquisa heurística "bidirecional" é investigada desde a década de 70, mas somente no final da década da 90 obtiveram-se resultados melhores que A*. Kaindl e Kainz em 1996 e 1997 mostram a pesquisa heurística bidirecional não simultânea, e o melhor uso possível da memória disponível em uma máquina. Já o algoritmo LCS* é apresentado por Johann, Caldwell, Kahng e Reis em 2000 e é o primeiro algoritmo de pesquisa heurística bidirecional simultânea com desempenho médio melhor que A*. Nesta palestra apresentaremos esses algoritmos e outros recentes avanços em pesquisa heurística, seus princípios de funcionamento, propriedades formais e desempenho, os quais têm inúmeras aplicações em variadas áreas da ciência da computação, como inteligência artificial, síntese de circuitos VLSI, trânsito, etc...