Node selection in retrace in pathfinding with the Lee algorithm


Creative Commons License

Duraklı Z., Nabiyev V.

2nd International Congress on Scientific Advances (ICONSAD’22), Konya, Turkey, 21 - 24 December 2022, pp.590-600

  • Publication Type: Conference Paper / Full Text
  • City: Konya
  • Country: Turkey
  • Page Numbers: pp.590-600
  • Erzincan Binali Yildirim University Affiliated: Yes

Abstract

Path planning algorithms are used in known environments to find the shortest, smooth and collision-free optimal path from the start point to the endpoint. One of these path-finding algorithms is the Lee algorithm. Although the Lee algorithm was originally developed to design copper paths in printed circuits, it is also used in path planning for autonomous vehicles. However, choices in return path preferences pose a problem in this path planning process. The optimum path between two points without obstacles is a line segment. Based on this, in this paper, a new approach based on a virtual line is proposed for the solution of return path preference problems. First, grid maps are used to model the environment. Second, using the Lee algorithm, markings are made between the start and end points to determine the path nodes. Third, an intuitive virtual line connecting the start and end points is created for use in the retrace preference. Finally, the Lee algorithm offers three different node options in the retrace preferences. In order to choose the best of these nodes and optimize the path, the closest node to the virtual line is preferred. In this way, the preferences continue from the ending point until they reach the starting point. Looking at the results of the proposed approach, it has been proven to be effective in obtaining an optimum path between the start and end points in known environments.

Yol planlama algoritmaları, bilinen ortamlarda, başlangıç noktasından bitiş noktasına en kısa, sorunsuz ve çarpışma olmadan en uygun yolu bulmak için kullanılır. Bu yol bulma algoritmalarından bir tanesi de Lee algoritmasıdır. Lee algoritması orijinal olarak baskı devrelerde bakır yollar tasarlamak için geliştirilmiş olsa da otonom araçlar için yol planlamasında da kullanılmaktadır. Ancak, bu yol planlama sürecinde geri dönüş yol tercihlerindeki seçimler sorun teşkil etmektedir. Aralarında engel olmayan iki nokta arasındaki optimum yol bir doğru parçasıdır. Bundan yola çıkarak bu bildiride, geri dönüş yol tercih problemlerinin çözümü için sanal bir doğruya dayalı yeni bir yaklaşım önerilmiştir. İlk olarak, çevreyi modellemek için ızgara haritaları kullanılır. İkinci olarak, Lee algoritması kullanılarak başlangıç ve bitiş noktaları arasına yol düğümlerini belirlemek için işaretlemeler yapılır. Üçüncüsü, Geri dönüş tercihinde kullanılmak üzere başlangıç ve bitiş noktalarını birleştiren sezgisel bir sanal doğru oluşturulur. Son olarak, Lee algoritması geri dönüş tercihlerinde üç farklı düğüm seçeneği sunar. Bu düğümlerden en iyisini seçip yolu optimize etmek için, sanal doğruya en yakın düğüm tercih edilir. Bu şekilde tercihler, bitiş noktasından başlangıç noktasına ulaşana kadar devam eder. Önerilen yaklaşımın sonuçlarına bakıldığında, bilinen ortamlarda başlangıç ve bitiş noktaları arasında optimum bir yol elde etmede etkinliği kanıtlanmıştır.