Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale
While transportation is an age-old problem, new technologies for autonomy raise new possibilities and realities for coordination of hundreds or thousands of vehicles and robots: criss-crossing autonomous vehicles, faster/cheaper Amazon delivery, and robots warehouses for storage/sorting/fetching. Ho...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/156645 https://orcid.org/0000-0003-1897-7381 |
| _version_ | 1826191154875465728 |
|---|---|
| author | Yan, Zhongxia |
| author2 | Wu, Cathy |
| author_facet | Wu, Cathy Yan, Zhongxia |
| author_sort | Yan, Zhongxia |
| collection | MIT |
| description | While transportation is an age-old problem, new technologies for autonomy raise new possibilities and realities for coordination of hundreds or thousands of vehicles and robots: criss-crossing autonomous vehicles, faster/cheaper Amazon delivery, and robots warehouses for storage/sorting/fetching. How do we tackle these new optimization challenges? In this thesis, I highlight multiple levels of decision-making in large-scale transportation problems, ranging from assignment of tasks to collision-free path/motion planning and everything in between (e.g. order of goals, routing, order of crossing, lane changing, continuous acceleration control). As practical solutions must be obtained in limited time, we leverage machine learning policies embodying offline experience to improve decision making. However, as we find in coordination of autonomous vehicles, policy learning alone may accommodate highly nonlinear continuous system dynamics but is insufficient in addressing the combinatorial discrete decisions in high-dimensional multi-agent systems. Thus, we investigate a more effective paradigm for tackling multi-agent transportation problems which involves 1) identifying or designing well-suited search-based algorithms for the problem settings then 2) designing machine learning approaches for guiding and accelerating the search algorithm. For problems ranging from vehicle routing problems (VRPs) to multi-agent path finding (MAPF), we find that, while the design of well-suited search-based algorithm is important, deep neural networks policies consistently accelerates or improves the solution quality of state-of-the-art search algorithms while eliminating the need for hand-designed search heuristics. With extensive empirical evaluations, we demonstrate that such learned policies often generalize beyond their training distributions to broader problem distributions. Finally, we return to the problem of autonomous vehicle coordination to design efficient search algorithms leveraging the structures of crossing orders at intersections with continuous vehicle kinematics, motivating further research in learning-guided crossing order search and semi-centralized coordination of vehicles/robots. |
| first_indexed | 2024-09-23T08:51:39Z |
| format | Thesis |
| id | mit-1721.1/156645 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:51:39Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1566452024-09-04T03:59:14Z Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale Yan, Zhongxia Wu, Cathy Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science While transportation is an age-old problem, new technologies for autonomy raise new possibilities and realities for coordination of hundreds or thousands of vehicles and robots: criss-crossing autonomous vehicles, faster/cheaper Amazon delivery, and robots warehouses for storage/sorting/fetching. How do we tackle these new optimization challenges? In this thesis, I highlight multiple levels of decision-making in large-scale transportation problems, ranging from assignment of tasks to collision-free path/motion planning and everything in between (e.g. order of goals, routing, order of crossing, lane changing, continuous acceleration control). As practical solutions must be obtained in limited time, we leverage machine learning policies embodying offline experience to improve decision making. However, as we find in coordination of autonomous vehicles, policy learning alone may accommodate highly nonlinear continuous system dynamics but is insufficient in addressing the combinatorial discrete decisions in high-dimensional multi-agent systems. Thus, we investigate a more effective paradigm for tackling multi-agent transportation problems which involves 1) identifying or designing well-suited search-based algorithms for the problem settings then 2) designing machine learning approaches for guiding and accelerating the search algorithm. For problems ranging from vehicle routing problems (VRPs) to multi-agent path finding (MAPF), we find that, while the design of well-suited search-based algorithm is important, deep neural networks policies consistently accelerates or improves the solution quality of state-of-the-art search algorithms while eliminating the need for hand-designed search heuristics. With extensive empirical evaluations, we demonstrate that such learned policies often generalize beyond their training distributions to broader problem distributions. Finally, we return to the problem of autonomous vehicle coordination to design efficient search algorithms leveraging the structures of crossing orders at intersections with continuous vehicle kinematics, motivating further research in learning-guided crossing order search and semi-centralized coordination of vehicles/robots. Ph.D. 2024-09-03T21:14:20Z 2024-09-03T21:14:20Z 2024-05 2024-07-10T13:02:22.685Z Thesis https://hdl.handle.net/1721.1/156645 https://orcid.org/0000-0003-1897-7381 Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Copyright retained by author(s) https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Yan, Zhongxia Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale |
| title | Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale |
| title_full | Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale |
| title_fullStr | Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale |
| title_full_unstemmed | Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale |
| title_short | Towards Learning-guided Search for Coordination of Multi-agent Transportation at Scale |
| title_sort | towards learning guided search for coordination of multi agent transportation at scale |
| url | https://hdl.handle.net/1721.1/156645 https://orcid.org/0000-0003-1897-7381 |
| work_keys_str_mv | AT yanzhongxia towardslearningguidedsearchforcoordinationofmultiagenttransportationatscale |