Robot path planning using intersecting convex shapes

Abstract

ÖZET Bu tezde içinde engeller olan bir ortamda robotun gideceği yörüngenin planlanması için bir algoritma geliştirilmiştir. Tezin genelinde şekillerinin dikdörtgensel olduğu varsayılan engellerle dolu iki boyutlu bir ortamdaki hareketli bir robot ele alınmıştır. Ayrıca robot bir nokta olarak kabul edilmiş ve bunun sonucu olarak da engeller minimum açıklık problemini çözmek için uygun şekilde büyütülmüştür. Sonra, hareketli robotu bir başlangıç noktasından bitiş noktasına engellere çarpmadan götürme problemi dinamik programlama yöntemine indirgenerek çözülmüştür. Bir yol ya da yol parçasına atanan maliyet doğrudan onun geometrik uzunluğu ile orantılıdır. Robotun bulunduğu nokta ve gitmesi istenen nokta geliştirilen algoritmaya girildiği zaman ilk önce bu iki nokta arasında engel olup olmadığı kontrol edilir. Eğer yoksa program son bulur. Aksi takdirde, engellerin başlangıç ve bitiş noktalarından görülen köşeleri bulunur. Bu köşelere sırasıyla başlangıç ve bitiş köşeleri denir. Sonra engellerin köşeleri arasındaki uzaklıklar bulunur. Bu hem `esas dışbükey alan` kavramı hem de dinamik programlama yöntemi kullanılarak yapılır. Esas dışbükey alan, içinde engel olmayan ve başka bir esas dışbükey alan tarafından kapsanmayan alandır. Bu nedenle aynı esas dışbükey alan içinde yer alan köşeler arasındaki uzaklık minimumdur. Aynı esas dışbükey alan içinde yer almayan köşeler arasındaki minimum uzaklık ise aynı dışbükey alan içinde yer alan köşelerin maliyetlerini kullanarak dinamik programlama yöntemi ile bulunur. Bundan sonra başlangıç ve bitiş köşe çiftleri arasındaki maliyetler bulunur. Minimum değerli köşe çifti aranan çözümü verir.

iv ABSTRACT In this thesis, an algorithm is developed for robot path planning in a structured environment. In the context of the thesis, a mobile robot is considered in a two dimensional environment filled with obstacles which are assumed to be rectangular in shape. Furthermore the robot is treated as a point and consequently the obstacles are grown appropriately to provide for minimum clearance problem. Then the problem of finding a collision free path that takes a mobile robot from an initial to a destination point is solved by reducing the problem to dynamic programming. The cost allocated to a path or a portion of a path is directly proportional to its geometric length. Given the source and destination points, the developed algorithm first checks if there are any obstacles between these points. If not, the program terminates.otherwise the corners of the obstacles that are visible from the source point, which are called source corners, and from the goal point, which are called destination corners, are obtained. After this step, the costs between the corners of the obstacles are found. This is done by using both the concept of `prime convex area` and the method of dynamic programming. A prime convex area is an area that is free of obstacles and is not fully incorporated in any other single prime convex area. So the distance between the corners taking place at the same prime convex area is optimal. The optimal distance between the corners not taking place at the same prime convex area is obtained by combining the costs found previously between the corners taking place at the same prime convex area and using the method of dynamic programming. After this step, the costs of the pairs of the source and destination corners are found. The corner pair with the minimum cost is the desired solution.