University of Twente Student Theses
Loop-breaking Approaches for Vehicle Route Planningwith Multi-agent Q-routing
Meerhof, J.J. (2021) Loop-breaking Approaches for Vehicle Route Planningwith Multi-agent Q-routing.
|
PDF
8MB |
| Abstract: | Computation of vehicle routes between locations in urban road networks is challenging due to the highly changing dynamics of vehicle traffic patterns. Reinforcement Learning (RL) is a powerful machine learning approach that can be exploited to develop autonomic control components in dynamic environments. Q-routing is an RL-based adaptive routing algorithm, originally proposed to improve packet routing in network communications. Q-routing can be exploited to self-adaptively compute vehicle routes in dynamic traffic scenarios. The Q-routing algorithm updates Q-tables to learn and predict travel times between road junctions. During the exploration stage, path tracking from the Q-tables may behave as a random walk from the source to the destination. However, if a loop is formed in multi-agent Q-routing, path tracking might loop forever until Q-table entries for the offending "loop nodes" are updated by another agent. Therefore, the formed loop must be broken somehow in order to find a simple (loopless) route path. In this research, four different approaches will be experimented with. This is done with the goal of breaking loops in Q-routing vehicle routing. The four different approaches are Loop-Erased Self-Avoiding Random, Negative Reward Function, Dual Reinforcement Learning and N-Learning. This is done with the goal of finding the most effective approach that leads to the shortest vehicle routes. In this paper the self defined N-learning algorithm combined with Dual Reinforcement Learning and the Negative Reward Function proved to be the most effective at lessening route loops and provided the vehicles with the shortest routes out of the different variations tested. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 54 computer science |
| Programme: | Computer Science BSc (56964) |
| Link to this item: | https://purl.utwente.nl/essays/86888 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page