التفاصيل البيبلوغرافية
| العنوان: |
Coordinated Path Planning through Local Search and Simulated Annealing. |
| المؤلفون: |
Yang, Hyeyun, Vigneron, Antoine |
| المصدر: |
Journal of Experimental Algorithmics (JEA); Dec2022, Vol. 27, p1-14, 14p |
| مصطلحات موضوعية: |
COMPUTATIONAL geometry, POTENTIAL field method (Robotics), SIMULATED annealing, ROBOTS, MOBILE robots |
| مستخلص: |
The third computational geometry challenge was on a coordinated path planning problem in which a collection of square robots need to move on the integer grid, from their given starting points to their target points, and without collision between robots, or between robots and a set of input obstacles. We designed and implemented three algorithms for this problem. First, we computed a feasible solution by placing middle-points outside of the minimum bounding box of the starting positions, the target positions and the obstacles, and moving each robot from its starting point to its target point through a middle-point. Second, we applied a simple local search approach where we repeatedly delete and insert again a random robot through an optimal path. It improves the quality of the solution, as the robots no longer need to go through the middle-points. Finally, we used simulated annealing to further improve this feasible solution. We used two different types of moves: We either tightened the whole trajectory of a robot, or we stretched it between two points by making the robot move through a third intermediate point generated at random. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of Experimental Algorithmics (JEA) is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
