BDD数据建模的路径规划算法  

Path Planning Algorithm Based on BDD

作　　者：彭雅丽[1] 廖雯婧[2] 尹红[1] 徐虹[1] 刘嘉遥 

机构地区：[1]江西师范大学软件学院,江西南昌330022 [2]江西理工大学研究生院,江西赣州341000

出　　处：《昆明理工大学学报（自然科学版）》2015年第2期67-72,共6页Journal of Kunming University of Science and Technology(Natural Science)

基　　金：国际合作重大专项(2010DFB90460);国家自然科学基金项目(61363077);江西省青年科学基金项目(20122BAB211037)

摘　　要：针对道路交通状态高动态性和不确定性的路径规划问题,提出一种基于BDD建模的启发式初始路径规划、增量重规划算法与A*搜索算法.首先利用基于BDD的启发式搜索进行全局规划,求解路网中车辆的最优路径集.基于BDD的启发式搜索利用BDD这一紧凑的数据结构来表示迁移状态空间,又通过启发信息进一步压缩搜索空间的大小;当路网信息发生变化时,按不同拥堵状况分类进行BDD迁移关系的修改,并进行增量重规划,重新获得当前状态至目标状态的最优路径集.仿真实验结果表明:基于BDD的启发式搜索和增量重规划,在求解路网信息动态不确定性下的车辆路径规划问题上具有高效性和实用性,避免了交通路网长时间陷入拥堵状态.Aimed at the high dynamics and uncertainty of road traffic,a BDD （binary decision diagram）-based heuristic algorithm is proposed to do the initial path planning,which is then combined with incremental replan-ning and A＊ algorithm to solve the route replanning problem.In order to get the optimal path set,BDD -Based heuristic Search is firstly used for global planning.Since BDD is a compact data structure,the BDD -Based heuristic Search uses it to represent the transition space and compress the search space through heuristic informa-tion at the same time;when the road network information changes,incremental replanning is used in different types of congestion and the optimum path is set again.The simulation results show that the BDD -Based heuris-tic Search and incremental replanning method has high efficiency and practicability in solving vehicle routing problem under dynamic and uncertain environment.

关 键 词：动态不确定环境 车辆路径规划 基于 BDD 的启发式搜索 增量重规划 

分 类 号：TP491[自动化与计算机技术]