Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming
Path planning is one of the issues to be handled in the development of autonomous systems. For a group of agents, cooperative path planning is crucial to ensure that a given mission is accomplished in the shortest time possible with optimal solution. Optimal means that the resulting path has minimal...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Asian Research Publishing Network (ARPN).
2016
|
| Subjects: | |
| Online Access: | http://eprints.uthm.edu.my/4235/1/AJ%202016%20%2826%29.pdf |
| _version_ | 1825709805858193408 |
|---|---|
| author | Che Ku, Nor Azie Hailma Omar, Rosli Sabudin Elia Nadira, Sabudin Elia Nadira |
| author_facet | Che Ku, Nor Azie Hailma Omar, Rosli Sabudin Elia Nadira, Sabudin Elia Nadira |
| author_sort | Che Ku, Nor Azie Hailma |
| collection | UTHM |
| description | Path planning is one of the issues to be handled in the development of autonomous systems. For a group of agents, cooperative path planning is crucial to ensure that a given mission is accomplished in the shortest time possible with optimal solution. Optimal means that the resulting path has minimal length hence the total consumed energy by the agents is the least. Cooperative path planning fuses information from all agents to plan an optimal path. There are a number of cooperative path planning methods available in the literature for multi-agent including Cell Decomposition, Roadmap and Potential Field to name but three. This paper will review and compare the performances of those existing methods that can find solution without graph search algorithm such as Mixed-Integer Linear Programming (MILP) techniques which exactly solves the problem and then propose four alternative MILP formulations which are computationally less intensive and suited for real-time purposes, but yield a theoretically guaranteed suboptimal solution. |
| first_indexed | 2024-03-05T21:48:00Z |
| format | Article |
| id | uthm.eprints-4235 |
| institution | Universiti Tun Hussein Onn Malaysia |
| language | English |
| last_indexed | 2024-03-05T21:48:00Z |
| publishDate | 2016 |
| publisher | Asian Research Publishing Network (ARPN). |
| record_format | dspace |
| spelling | uthm.eprints-42352021-12-01T07:09:02Z http://eprints.uthm.edu.my/4235/ Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming Che Ku, Nor Azie Hailma Omar, Rosli Sabudin Elia Nadira, Sabudin Elia Nadira TJ210.2-211.47 Mechanical devices and figures. Automata. Ingenious mechanisms. Robots (General) Path planning is one of the issues to be handled in the development of autonomous systems. For a group of agents, cooperative path planning is crucial to ensure that a given mission is accomplished in the shortest time possible with optimal solution. Optimal means that the resulting path has minimal length hence the total consumed energy by the agents is the least. Cooperative path planning fuses information from all agents to plan an optimal path. There are a number of cooperative path planning methods available in the literature for multi-agent including Cell Decomposition, Roadmap and Potential Field to name but three. This paper will review and compare the performances of those existing methods that can find solution without graph search algorithm such as Mixed-Integer Linear Programming (MILP) techniques which exactly solves the problem and then propose four alternative MILP formulations which are computationally less intensive and suited for real-time purposes, but yield a theoretically guaranteed suboptimal solution. Asian Research Publishing Network (ARPN). 2016 Article PeerReviewed text en http://eprints.uthm.edu.my/4235/1/AJ%202016%20%2826%29.pdf Che Ku, Nor Azie Hailma and Omar, Rosli and Sabudin Elia Nadira, Sabudin Elia Nadira (2016) Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming. ARPN Journal of Engineering and Applied Sciences, 11 (14). pp. 8921-8926. ISSN 1819-6608 |
| spellingShingle | TJ210.2-211.47 Mechanical devices and figures. Automata. Ingenious mechanisms. Robots (General) Che Ku, Nor Azie Hailma Omar, Rosli Sabudin Elia Nadira, Sabudin Elia Nadira Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming |
| title | Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming |
| title_full | Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming |
| title_fullStr | Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming |
| title_full_unstemmed | Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming |
| title_short | Recent research in cooperative path planning algorithms for multi-agent using mixed- integer linear programming |
| title_sort | recent research in cooperative path planning algorithms for multi agent using mixed integer linear programming |
| topic | TJ210.2-211.47 Mechanical devices and figures. Automata. Ingenious mechanisms. Robots (General) |
| url | http://eprints.uthm.edu.my/4235/1/AJ%202016%20%2826%29.pdf |
| work_keys_str_mv | AT chekunoraziehailma recentresearchincooperativepathplanningalgorithmsformultiagentusingmixedintegerlinearprogramming AT omarrosli recentresearchincooperativepathplanningalgorithmsformultiagentusingmixedintegerlinearprogramming AT sabudinelianadirasabudinelianadira recentresearchincooperativepathplanningalgorithmsformultiagentusingmixedintegerlinearprogramming |