基于智能符号回归的路径规划A^＊算法均衡控制方法

A Trade-off Control Approach for A^＊ Algorithm Based on Intelligent Symbolic Regression

随着地图网站和在线导航系统的普及,多用户网络并发出行信息查询服务的需求日益增长。如何满足多用户并发路径查询效率需求,同时又使得路径查询精度可控,是网络地理信息服务的瓶颈技术问题。本文提出了一种多用户并发路径查询精度效率均衡控制方法,利用系统抽样和智能符号回归技术,根据动态变化的在线路径查询用户规模和系统响应效率容忍阈值,在经典的路径查询A*启发式算法基础上,根据大样本确定的路径查询严密算法和对应启发式算法得到的系统耗时比和精度比,实时自动确定启发式路径查询启发因子权重,有效平衡多用户并发路径查询的响应效率和精度损失,自适应地控制路径查询算法的精度和效率之间的平衡,在精度预先可控的前提下,最大限度地提升多用户并发路径查询效率,缩短用户的路径查询等待时间。

With the widespread use of map websites and on-line navigation systems, the need for multi-user concurrent queries for travel information is ever-increasing. In such a case, a bottleneck problem is how to improve the efficiencies of the multi-user concurrent path queries as much as possible, with only a controllable, as little as possible loss of the precisions of the query results. In this paper, an efficiency/accuracy trade-off control approach for the A^＊ heuristic shortest path algorithm is presented, which fits a curve function of the heuristic factor, the efficiency and the accuracy with large samples, by the techniques of systematic sampling and intelligent symbolic regression. The efficiency and the accuracy of the A^＊ algorithm are measured by the comparison with the Dijkstra exact algorithm. Through the use of the derived trade-off control model, the effective heuristic factor can be automatically determined with the input of the on-line user number and the required path accuracy, and as a result, the service response time for each user is much shortened.