Data center's crusing robot paths planning method based on improved Ant Colony SystemTechnical field
The present invention relates to crusing robot technical fields, more particularly to data center's inspection based on improved Ant Colony SystemRobot path planning method.
Background technique
Data center replaces manually carrying out inspection to the instrumentation in data center using crusing robot at present, withThe problems such as overcoming the high heavy workload faced in manual inspection, danger coefficient, low efficiency and poor reliability.Wherein path planning isCan crusing robot efficiently complete the basis of patrol task, while affect the intelligence degree and performance of crusing robot.The local paths planning and global path planning of the crusing robot of data center's laser navigation at present all use dijkstra's algorithm,This method is only being considered locally the optimal of path, but does not consider that path is optimal from the overall situation, and it is more that there are duplicate paths, alwaysThe longer disadvantage of polling path, while encountering after obstacle regardless of whether patrol task terminates just to stop inspection, lack independence, nothingMethod fully demonstrates the intelligence of crusing robot.Data center's crusing robot also has using dijkstra's algorithm regional planning agency simultaneouslyGlobal path is planned in portion path, simulated annealing, and this method is at task points fewer (being lower than 100), the consumption of planningWhen and path length all relatively rationally, but when task point increases, this method is not suitable for large-scale inspection just than relatively time-consumingTask.
In this field, it is complete that a kind of crusing robot based on topology point classification is introduced in Chinese 201510290471.5th inventionOffice's paths planning method carries out classification merging according to said path by the topology point of anchor point, establishes the oriented of corresponding topology pointOriented diagram data knot is then only inserted into path planning later in robot current location and target position topology point by data structureStructure can significantly reduce and participate in calculating method topology point quantity, improve the computational efficiency of path planning and reduction disappears to memory spaceConsumption, still, the path planning algorithm currently based on laser navigation crusing robot are the bases that relationship is digraph between topology pointIt is planned on plinth, whether it is more that there are duplicate paths, and total path is longer, and terminate just to stop at once regardless of patrol task after meeting barrierOnly original place no longer inspection, cannot according to the executive condition of patrol task it is autonomous carry out judge and plan new polling path, andAnd at present in the path planning algorithm scheme of some data center's crusing robots, when task point quantity is more, path ruleIt draws just than relatively time-consuming, in addition, there are no realize that robot is met to hinder in the paths planning method of data center's crusing robot at presentDecide whether that there is also the task of non-inspection points according to the inspection situation of task afterwards, and its path is planned again, to guarantee to patrolThe satisfactory completion of inspection task, for this purpose, we have proposed data center's crusing robot path rule based on improved Ant Colony SystemThe method of drawing solves the above problems.
Summary of the invention
The purpose of the present invention is to solve disadvantage existing in the prior art, and propose based on improved Ant Colony SystemData center's crusing robot paths planning method.
To achieve the goals above, present invention employs following technical solutions:
Data center's crusing robot paths planning method based on improved Ant Colony System, comprising the following steps:
S1, initialization information, while reading shortest distance matrix and arest neighbors square between the whole station all the points kept in advanceBattle array；
S2, it is numbered according to current task point, obtains corresponding shortest distance matrix；
S3, improved ant group algorithm planning path, acquisition task point sequence are utilized；
S4, in conjunction with arest neighbors matrix, task point sequence is refined, with guarantee crusing robot can according to path intoThe correct inspection of row, completes patrol task；
During S5, robot carry out inspection according to the path sequence of planning, the moment is detected whether with the presence of obstacle；Such asFruit does not encounter barrier, executes step 12；If there is barrier, step 6 is executed；
S6, judge whether that there are also the task points not detected, if so, thening follow the steps 7；If not, thening follow the steps 13；
S7, the chance barrier position that robot is presently in is obtained, is accurately updated between whole station all the points according to barrier position is metTopological structure, while the closest point at robot chance barrier is obtained as new starting point and remaining not detecting for taskPoint；
S8, judge whether isolated point occur, that is, after there is obstacle, if the task that no feasible path can reach occurPoint, if so, executing step 9；If not, executing step 10；
S9, the isolated point occurred is rejected, updates cartographic information, obtained the topological matrix between remaining all the points, then executeStep 11；
S10, cartographic information is updated, obtains the topological matrix between whole station all the points, then execute step 11；
S11, newest distance matrix and arest neighbors matrix are obtained, then executes step 2；
S12, judge whether that inspection terminates, if inspection terminates, then follow the steps 13；If the not described end of inspection,Execute step 5；
S13, end, robot stop inspection, wait and instructing in next step.
Preferably, whole station all the points are to rely on point and task point in described S1, S7, S9 and S10.
Preferably, in the S3, improved ant group algorithm is that ant group algorithm is combined with neighborhood search.
Preferably, in the S1, shortest path matrix and topological matrix between whole station all the points are main symmetrical matrix.
Preferably, in the S11, main symmetrical matrix uses dijkstra's algorithm operation.
Preferably, in the S1, task point quantity is 800-1500.
Preferably, in the S1, the initialization information includes starting point, terminal, task point quantity and task point number.
In the present invention, first by initialization information, i.e. starting point, terminal, task point quantity, task point number, read simultaneouslyShortest distance matrix and arest neighbors matrix between the whole station all the points kept in advance are numbered according to current task point, obtain phaseCorresponding shortest distance matrix recycles improved ant group algorithm planning path, task point sequence is obtained, in conjunction with arest neighbors squareBattle array, refines task point sequence, to guarantee that crusing robot can carry out correct inspection according to path, completes inspection and appointsBusiness is detected during then robot carries out inspection according to the path sequence of planning using the self-contained sensor momentWhether with the presence of obstacle, if not encountering barrier, step 13 is executed；If there is barrier, step 6 is executed, is then judgedWhether there are also the task points not detected, if so, thening follow the steps 7；If not, thening follow the steps 14, it is current to obtain robotLocating chance hinders position, accurately updates the topological structure between whole station all the points according to barrier position is met, while obtaining robot chanceA closest point and the remaining task point not detected at barrier, judge whether isolated point occur, that is, after there is obstacle, areThe no task point that no feasible path occurs and can reach, if so, executing step 9；If not, executing step 10, then pickExcept the isolated point of appearance, cartographic information is updated, the topological matrix between remaining all the points is obtained, then executes step 12, then updateCartographic information obtains the topological matrix between all the points, then executes step 12, is obtained with dijkstra's algorithm newest apart from squareThen battle array and arest neighbors matrix execute step 2, judge whether that inspection terminates, if inspection terminates, then follow the steps 14；IfInspection is not finished, and thens follow the steps 5, finally terminates, and robot stops inspection, waits and instructing in next step, the present invention can be in officeWhen business points are more, the time of planning path was controlled within one second, and duplicate paths significantly reduce, and total path is obviously shortened,It can independently be determined according to the performance of patrol task after meeting barrier simultaneously and plan new polling path again, the in addition calculationMethod has preferable robustness, in a word invention significantly improves the routing inspection efficiency of data center's laser navigation crusing robot,Crusing robot can be made to complete task to be inspected with the shorter time, at the same improve crusing robot degree of intelligence and fromMain property.
Detailed description of the invention
Fig. 1 is the solution process of data center's crusing robot paths planning method based on improved Ant Colony SystemFigure.
Specific embodiment
Following will be combined with the drawings in the embodiments of the present invention, and technical solution in the embodiment of the present invention carries out clear, completeSite preparation description, it is clear that described embodiments are only a part of the embodiments of the present invention, instead of all the embodiments.
Referring to Fig.1, data center's crusing robot paths planning method based on improved Ant Colony System, including following stepIt is rapid:
S1, initialization information, i.e. starting point, terminal, task point quantity, task point number, while reading keep complete in advanceShortest distance matrix and arest neighbors matrix between all the points of standing, whole station all the points are by point and task point, whole station all the pointsBetween shortest path matrix and topological matrix be main symmetrical matrix, task point quantity is 800-1500, the premise of the stepThe characteristics of being road information in combined data center, anchor point, task point and laser navigation mode, using topological structure logarithmMathematical modeling is carried out according to center environment map, by all anchor points and the undirected topological structure of task point in data centerIndicate the relationship between them, the distance between two points of direct neighbor are the actual range in scene；
S2, it is numbered according to current task point, obtains corresponding shortest distance matrix；
S3, using improved ant group algorithm planning path, obtain task point sequence, improved ant group algorithm is mostNeighborhood search is added on the basis of basic ant group algorithm, efficiency of algorithm can be greatly improved by adding neighborhood search strategy,Allow to the large-scale task points of faster speed planning, to break through merely by the not applicable of original ant group algorithmIn the limitation of extensive task points, while it can solve the path planning of current data center's laser navigation crusing robotThe problem of algorithm；
S4, in conjunction with arest neighbors matrix, task point sequence is refined, with guarantee crusing robot can according to path intoThe correct inspection of row, completes patrol task；
During S5, robot carry out inspection according to the path sequence of planning, the moment is detected whether with the presence of obstacle；Such asFruit does not encounter barrier, executes step 12；If there is barrier, step 6 is executed；
S6, judge whether that there are also the task points not detected, if so, thening follow the steps 7；If not, thening follow the steps 13；
S7, the chance barrier position that robot is presently in is obtained, is accurately updated between whole station all the points according to barrier position is metTopological structure, while the closest point at robot chance barrier is obtained as new starting point and remaining not detecting for taskPoint；
S8, judge whether isolated point occur, that is, after there is obstacle, if the task that no feasible path can reach occurPoint, if so, executing step 9；If not, executing step 10；
S9, the isolated point occurred is rejected, updates cartographic information, obtained the topological matrix between remaining all the points, then executeStep 11；
S10, cartographic information is updated, obtains the topological matrix between whole station all the points, then execute step 11；
S11, newest distance matrix and arest neighbors matrix are obtained, then executes step 2, obtained main symmetrical matrix and useDijkstra's algorithm operation；
S12, judge whether that inspection terminates, if inspection terminates, then follow the steps 13；If the not described end of inspection,Execute step 5；
S13, end, robot stop inspection, wait and instructing in next step.
In the present invention, first by initialization information, i.e. starting point, terminal, task point quantity, task point number, read simultaneouslyShortest distance matrix and arest neighbors matrix between the whole station all the points kept in advance are numbered according to current task point, obtain phaseCorresponding shortest distance matrix recycles improved ant group algorithm planning path, task point sequence is obtained, in conjunction with arest neighbors squareBattle array, refines task point sequence, to guarantee that crusing robot can carry out correct inspection according to path, completes inspection and appointsBusiness is detected during then robot carries out inspection according to the path sequence of planning using the self-contained sensor momentWhether with the presence of obstacle, if not encountering barrier, step 13 is executed；If there is barrier, step 6 is executed, is then judgedWhether there are also the task points not detected, if so, thening follow the steps 7；If not, thening follow the steps 14, it is current to obtain robotLocating chance hinders position, accurately updates the topological structure between whole station all the points according to barrier position is met, while obtaining robot chanceA closest point and the remaining task point not detected at barrier, judge whether isolated point occur, that is, after there is obstacle, areThe no task point that no feasible path occurs and can reach, if so, executing step 9；If not, executing step 10, then pickExcept the isolated point of appearance, cartographic information is updated, the topological matrix between remaining all the points is obtained, then executes step 12, then updateCartographic information obtains the topological matrix between all the points, then executes step 12, is obtained with dijkstra's algorithm newest apart from squareThen battle array and arest neighbors matrix execute step 2, judge whether that inspection terminates, if inspection terminates, then follow the steps 14；IfInspection is not finished, and thens follow the steps 5, finally terminates, and robot stops inspection, waits and instructing in next step.
The foregoing is only a preferred embodiment of the present invention, but scope of protection of the present invention is not limited thereto,Anyone skilled in the art in the technical scope disclosed by the present invention, according to the technique and scheme of the present invention and itsInventive concept is subject to equivalent substitution or change, should be covered by the protection scope of the present invention.