The Study on Development and Applicability of Knowledge-Based Learning Algorithm for Route Guidance

本课题旨在对分布式导航系统的学习算法进行基础研究。通过理论分析和数值分析两方面的研究，得出了当所有驾驶员都使用该算法时要实现的交通均衡的一个特性的重要结果。我们的方法的基本假设是，每个司机根据自己的日常经验获得的旅行信息来选择他或她的路线。然而，旅行信息，比如从出发地到目的地的旅行时间，可能会随机波动，受到其他司机选择的影响。即使在这种情况下，如果每个驾驶员按照后悔匹配规则选择路线，也可以达到一定的稳定状态。这一结论与传统的Wardrop均衡概念有很大的不同，后者假设驾驶员的信息是完全的。这一结论表明，一个精心设计的信息采集系统可以使交通系统稳定，使司机熟悉最佳路线。实现这一功能的核心引擎可能被称为智能驾驶算法。智能驾驶算法由马尔可夫决策过程和后悔匹配算法相结合组成。数值计算的效率取决于近似动态规划理论和随机逼近算法。我们通过将其应用于一个简单的网络来测试算法，但是，我们假设可能现实的是链路成本函数。在所有情况下，我们都取得了成功的结果；然而，趋同的速度非常缓慢。本研究提出了分布式车辆导航系统的可能性，即单个驾驶员使用GPS自行收集出行信息，并通过机器学习自动引导到更好的路线。

This study aims a fundamental study of the learning algorithm to develop a distributed navigation system. The study was conducted through both theoretical and numerical analysis, and obtained significant results about a characteristic of the traffic equilibrium to be realized when all drivers used this algorithm. The basic assumption of our approach is that each individual driver chooses his or her route based on travel information obtained by one's daily experience. Travel information, far instance a travel time to a destination from an origin of a trip, however, can fluctuate stochastically to be affected by the choice of other drivers. Even with such a situation, each driver can reach a certain stable state if he chooses a route according to the regret matching rule. This conclusion is fir different from the conventional concept of Wardrop equilibrium where drivers' perfect information is assumed. This conclusion implies that a carefully designed information acquisition system allows the transportation system being stable and drivers to acquaint the best route.The core engine that enables this maybe called the intelligent driving algorithm. The intelligent driving algorithm consists of a combination of Markov decision process and the regret matching algorithm. The efficiency of numerical calculation depends on the theory of approximate dynamic programming and stochastic approximation algorithm. We tested the algorithm by applying it to a simple network, but, we assumed possibly realist is link cost functions. For all cases, we obtained successful results; however, the rate of convergence was very slow.This study suggests the possibility of the distributed vehicle navigation system, in which an individual driver collects travel information by self with using GPS and is automatically guided by machine learning to a better route.