O Simulated Annealing é um algoritmo de otimização baseado na exploração Monte Carlo de um espaço n-dimensional. Podemos citar duas características importantes dos algoritmos: a primeira é que ele procura em um espaço contínuo com um custo que não cresce com a complexidade do espaço considerado; a segunda é que ele pode evitar mínimos locais não-globais, gerando soluções que são pelo menos quase-ótimas. Assim sendo, ele é indicado para o planejamento de trajetórias em ambientes cuja decomposição é computacionalmente complexa, pois trabalha diretamente sobre o espaço contínuo. Como o Simulated Annealing não tem problemas em lidar com tais ambientes, o problema de encontrar uma trajetória ótima se transforma em um problema de otimização de uma função que estima o custo total da trajetória. Assim sendo, a proposta deste trabalho é utilizar o Simulated Annealing - melhorado por um conjunto de heurísticas - para planejar trajetórias poligonais com baixo custo em espaços contínuos. Faz-se comparações de desempenho tanto entre várias implementações do Simulated Annealing quanto entre ele e uma resolução de enfoque diverso: configuração espacial seguida de busca em grafos. Com tudo isto, avalia-se o efeito de cada regra heurística no aprimoramento do algoritmo Simulated Annealing e quando a aplicação deste se justifica.

Simulated Annealing is an optimisation process based on the Monte Carlo exploration of an n-dimensional space. It has two characteristics of interest to this work: it explores continuous space with a cost that grows less than the complexity of the considered space; second, it is able to avoid non-global local minima, yielding results that are at least near optimal. It is thus suited for planning trajectories in environments whose decomposition is computationally complex (for it does not need one at all, as it works over the continuous space itself). As Simulated Annealing has no problem dealing with such environments, it can be applied to the problem of finding an optimal trajectory, by minimising the function that estimates the total cost of the trajectory. Our proposal, then, is to use Simulated Annealing - powered by a set of improvements - to plan low-cost, polygonal trajectories in continuous spaces. Performance comparisons are made, both between many Simulated Annealing implementations and between Simulated Annealing and a different approach: spatial configuration followed by graph searching. Then the effect of each heuristic rule on the performance of the Simulated Annealing algorithm is evaluated. Last, conclusions about when Simulated Annealing should be used are made.