بهبود مسير توليد شده در درختهاي چهار تايي و هشت تايي در مساله مسيريابي، با استفاده از يك الگوريتم حريصانه مبتني بر امتيازدهي بر اساس روش شباهت به ايده آل

Enhancing Generated Paths in Quadtrees and Octrees in Path Planning Problem, Using a Greedy Algorithm Based on TOPSIS

استفاده از ربات ها، روز به روز توجه بيشتري به خود جلب مي كنند. يكي از مسائل مهم مورد توجه محققين چگونگي هدايت اين ربات ها است. مسيريابي يكي از مهم ترين مسائل مورد نياز براي هدايت ربات ها است. يكي از رويكردهاي مسيريابي، استفاده از درخت هاي چهار تايي و هشت تايي جهت مدل كردن محيط است. استفاده از اين ساختارها، تاثير منفي بر بهينگي مسير ايجاد مي كند. براي حل اين مشكل درخت هاي چهارتايي و هشت تايي حاشيه دار معرفي شده اند ولي اين ساختار نيز منجر به افزايش تعداد گره هاي درخت مي گردد. در اين مقاله، روشي جديد براي ايجاد مسير در درختهاي هشت تايي و چهارتايي ارائه شد كه قادر به رفع مشكل ايجاد مسيرهاي طولاني در اثر استفاده از اين ساختارها است. مثال هاي عددي اجرا شده، برتري نسبي ميانگين نتيجه حاصل شده از روش پيشنهادي ايجاد مسير به ازاي تمام مجموعه پارامترهاي استفاده شده و كاهش حدودا 50 درصدي بيشنه زاويه طي شده و حدودا 15 درصدي مسافت مسير را در صورت استفاده از مجموعه پارامترهاي منتخب، نسبت به استفاده از روش معمول ايجاد مسير نشان مي دهد

Using robots is increasingly gaining attention. One of important aspects of them is how to guide robots. Path planning is one of essential parts of robots guidance. Among all approaches in path planning, using quadtrees and octrees to model the environment leads to negative effect on the length of the path generated. To overcome this shortcoming, framed quadtrees and octrees have been presented but they also cause an increase in the number of nodes of tree. In this paper, a new method is presented to generate paths in classic quadtrees and octrees, which can eliminate the negative effect of using these structures on length of the generated path. Experimental results illustrate that proposed method has slightly better outputs than the normal path generation in average and reduces about 50 percent the maximum angle and 15 percent the length of the generated path in the case of using optimal parameters