Fast Planning of Intelligent Vehicle Trajectories under Multi-Constraints

本文主要围绕智能飞行器航迹规划问题，基于飞行器飞行过程中产生的水平误差、垂直误差、校正点位置，校正点处的校正类型以及校正概率等约束要求，结合题目中给出的校正点的坐标数据，规划从起始点到终点的最优路径。本文利用不等式抽象出相关约束条件，构建路径动态规划模型、0-1规划模型、分层规划模型，并运用改进的Dijkstra智能算法来寻找智能飞行器的最优航行轨迹；此外，考虑到实际情况，在有一定概率校正失败条件下，权衡模型与校正点数量和航迹长短之间的关系，让飞行器通过校正点最少，从而使得最后寻找到的最优路径更加符合真实情况。问题的难点在于在保证误差的前提下，使得飞行器航行路径通过校正点的次数最少且航迹最短。本文首先将飞行器飞行过程看作一个误差累积的过程，并依据各个校正点的校正类型，结合初始点到其余各校正点之间的距离误差准则，筛选出初始点到各点的最优距离，然后根据待选取校正点，将误差约束条件与改进的图论Dijkstra算法进行融合，从而规划出最优航迹，使得飞行器在经过校正点次数最少同时航迹的距离也最短。在数据集一、二中，最优航迹距离分别为106802.676米和118,730.036米。This paper mainly focuses on the intelligent vehicle trajectory planning problem, based on the constraint requirements such as horizontal error, vertical error, location of correction point, type of correction at the correction point and probability of correction generated during the flight of the vehicle, combined with the coordinate data of the correction point given in the title, to plan the optimal path from the start point to the end point. In this paper, we use inequalities to abstract the relevant constraints, construct the path dynamic planning model, 0-1 planning model, and hierarchical planning model, and apply the improved Dijkstra intelligent algorithm to find the optimal trajectory of the intelligent vehicle. In addition, taking into account the actual situation, under the condition of a certain probability of correction failure, the relationship between the model and the number of correction points and the length of the trajectory is weighed so that the aircraft passes through the least number of correction points, and thus the optimal paths found are more consistent with the real situation. The difficulty of the problem is to minimize the number of correction points and shortest trajectory under the premise of guaranteeing the error. In this paper, we first regard the flight process of the aircraft as a process of error accumulation, and according to the correction type of each correction point, combined with the distance error criterion between the initial point and the rest of the correction points, we filter out the optimal distance from the initial point to each point, and then according to the correction points to be selected, we integrate the error constraints with the improved graph theoretic Dijkstra algorithm, so as to plan the optimal trajectory, which makes the vehicle pass through correction points the least number of times and have the shortest trajectory. In data sets I and II, the optimal trajectory distances are 106802.676 meters and 118730.036 meters, respectively.