Otimização discreta na determinação de trajetórias de veículos Dubins
Resumo
Veículos Dubins são veículos que descrevem curvas duas vezes diferenciáveis com restrição de curvatura. Nesse trabalho investigamos um algoritmo para o Problema do Caixeiro Viajante de veículos Dubins. Para isto, propomos o uso de uma versão do Problema do Caixeiro Viajante que minimiza distâncias e ângulos de mudança de direção para determinar a ordem em que os pontos são visitados. Para calcular as curvas Dubins ponto-a-ponto, usamos o teorema de Dubins, e aplicamos um algoritmo de caminho mínimo em um espaço de busca discretizado. Os resultados indicam que o novo algoritmo obtém soluções melhores do que as encontradas na literatura.
Referências
Aggarwal, A., D. Coppersmith, S. Khanna, R. Motwani, and B. Schieber, The angularmetric traveling salesman problem, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (1997), 221–229.
Dubins, L.E., On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents American Journal of Mathematics 79 (1957), 497–516.
Dantzig, G.B., D.R. Fulkerson, and S.M. Johnson, Solution of large scale traveling salesman problem, Oper.Res. 2 (1954), 393–410.
LaValle, S.M., “Planning Algorithms”, Cambridge University Press (2006) (também disponível em [link]).
Le Ny, J., E. Frazzoli, and E. Feron, The curvature-constrained traveling salesman problem for high point densities, IEEE Conf. on Decision and Control (2007), 5985–5990.
Savla, K., E. Frazzoli, and F. Bullo, On the point-to-point and traveling salesperson problems for Dubins’ vehicle, American Control Conference, Portland, OR (2005), 786–791.
Shkel, A.M., and V. J. Lumelsky, Classification of the Dubins set, Robotics and Autonomous Systems (2001), vol. 34, 179–202.
Dubins, L.E., On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents American Journal of Mathematics 79 (1957), 497–516.
Dantzig, G.B., D.R. Fulkerson, and S.M. Johnson, Solution of large scale traveling salesman problem, Oper.Res. 2 (1954), 393–410.
LaValle, S.M., “Planning Algorithms”, Cambridge University Press (2006) (também disponível em [link]).
Le Ny, J., E. Frazzoli, and E. Feron, The curvature-constrained traveling salesman problem for high point densities, IEEE Conf. on Decision and Control (2007), 5985–5990.
Savla, K., E. Frazzoli, and F. Bullo, On the point-to-point and traveling salesperson problems for Dubins’ vehicle, American Control Conference, Portland, OR (2005), 786–791.
Shkel, A.M., and V. J. Lumelsky, Classification of the Dubins set, Robotics and Autonomous Systems (2001), vol. 34, 179–202.
Publicado
20/07/2010
Como Citar
MEDEIROS, André César; URRUTIA, Sebastián.
Otimização discreta na determinação de trajetórias de veículos Dubins. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 29. , 2010, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 153-160.
