A kind of automatic path planning method and mobile robot of mobile robotTechnical field
The present invention relates to electronic robot technical fields, are to be related to a kind of automatic rule of mobile robot more specificallyDraw Path Method and mobile robot.
Background technique
Mobile robot (Mobile robot) is a kind of by sensor, remote manipulator and the mobile vehicle of automatic controlThe robot system of composition, is the product of the integrated application of an interdisciplinary study developed in recent years, it has concentrated mechanical, electricityThe multidisciplinary newest research results such as son, computer, automatic control and artificial intelligence, represent the highest of electromechanical integration atJust.Mobile robot has locomotive function, and dangerous, operation and the environment work less than people under adverse circumstances are being engaged in instead of peopleAspect has bigger mobility, flexibility than general robot.Mobile robot gradually using with industrial production agricultural,The different industries such as medical treatment.
In the research of mobile robot the relevant technologies, airmanship is its core, and path planning is navigation researchOne important link and project.So-called path planning refers to mobile robot according to a certain performance indicator (such as distance, time, energySource consumption etc.) optimal or sub-optimal path of the search one from initial state to dbjective state.The problem of path planning relates generally toIncluding: (1) establishes relatively reasonable model using the mobile robot environmental information of acquisition, then with certain algorithm find one fromInitial state is to optimal or near-optimization the collisionless path of dbjective state；(2) it is capable of handling uncertain in environmental modelThe error occurred in factor and path trace is minimized influence of the external object to robot；(3) using known allInformation carrys out the movement of guided robot, to obtain more preferably behaviour decision making relatively.Currently, for mobile robot path planningThe research of technology has been achieved for a large amount of achievement, and many scientists are studied from different aspect.Wherein, from robot pairThe research of the angle of environment sensing, method for planning path for mobile robot is divided into three types: the planning side based on environmental modelThe paths planning method of method, the planing method of vision based and Behavior-based control；The journey that environmental information is grasped from robotDegree, and global path planning based on environment priori Complete Information can be divided into and based on the local paths planning of sensor information；From the aspect of whether changing over time from planning environment, it can also be divided into static path planning and active path planning；From mobile machineOn the specific algorithm of people's path planning and strategy, planning technology can be divided into following four classes: stencil matching Path Planning Technique, artificialPotential field Path Planning Technique, map structuring Path Planning Technique and artificial intelligence Path Planning Technique.Artificial intelligence path planningTechnology be by modern artificial intelligence technology be applied to mobile robot path planning in, as artificial neural network, evolutionary computation,Fuzzy logic and swarm intelligence algorithm etc..Wherein, the Path Planning Technique based on artificial intelligence is research hotspot in recent years.
Glowworm swarm algorithm (Firefly Algorithm) is a kind of new intelligence proposed by Yang Xin-she in 2008Can optimization algorithm, the biological characteristics of fire fly luminescence develop in the algorithm simulation nature, with particle swarm algorithm andAnt group algorithm is the same and a kind of naturally heuristic Stochastic Optimization Algorithms based on group.The algorithm is once proposition, by the countryThe concern of outer scholar becomes a new research hotspot of computational intelligence research field, and the algorithm has been applied in function at presentOptimization, image procossing, Combinatorial Optimization, feature selecting, clustering, Stock Price Forecasting, protein structure prediction and dynamic cityThe research fields such as field price.The computational efficiency of existing firefly group algorithm is high, and memory overhead is small, and the parameter of adjusting is few, simplyIt is easily achieved, but the coefficient of disturbance α in existing glowworm swarm algorithm is usually fixed constant, this is for the search of algorithmBe it is defective, there is also Premature convergences as other random search algorithms.
Summary of the invention
It is an object of the invention to overcome drawbacks described above in the prior art, a kind of automatic planning of mobile robot is providedPath Method and mobile robot adjust the strategy of coefficient of disturbance based on Sobol sequence initialization population and dynamic, by rightCoefficient of disturbance in glowworm swarm algorithm carries out adaptive adjustment to enhance convergence energy, to improve mobile robotCarry out the ability of path planning.
To achieve the above object, first aspect present invention provides a kind of automatic path planning method of mobile robot,The following steps are included:
Acquire environmental information；
It is modeled by the region that collected environmental information is ready for path planning to mobile robot to constructTwo-dimensional plane coordinate figure, and determine the coordinate position of starting point, terminal and barrier；
Based on two-dimensional plane coordinate figure, mobile robot is passed through from the path of origin-to-destination based on Sobol sequenceInitialization of population and the glowworm swarm algorithm of dynamic adjustment coefficient of disturbance Population Regeneration carry out path optimizing, to sit in two-dimensional surfaceMark on a map it is middle planning plan to implement into path optimizing；
According to the path optimizing that planning is completed, mobile robot is driven to be moved.
Preferably, in the above-mentioned methods, described to be based on two-dimensional plane coordinate figure, to mobile robot fromPoint passes through the firefly of initialization of population and dynamic adjustment coefficient of disturbance Population Regeneration based on Sobol sequence to the path of terminalAlgorithm carry out path optimizing, thus in two-dimensional plane coordinate figure planning plan to implement into path optimizing the step of specifically include:
The basic parameter of glowworm swarm algorithm is imported, and initializes each basic parameter of glowworm swarm algorithm；
Using Sobol sequence initialization population, the position of popN firefly is generated, calculates the target letter of every fireflyNumber selects brightness maximum as optimal location to obtain corresponding brightness；
The Attraction Degree for calculating every firefly is guided the movement of other fireflies by the firefly with maximum brightness,The position of every firefly is updated, and recalculates the brightness of firefly；
It when reaching maximum search number, then exports optimum individual and stops algorithm, otherwise, recalculate every fireflyAttraction Degree.
Preferably, in the above-mentioned methods, the Sobol sequence is with 2 for base, by one group of direction number V1,V2, V3..., Vi..., VnIt generates, wherein Vi∈ (0,1), in Sobol sequence, the value of i-th of element jth dimension can be obtained by formulaIt arrives:
Preferably, in the above-mentioned methods, the calculation formula of the Attraction Degree of the firefly are as follows:
In formula, β0Attraction when be two firefly distances being zero, γ is the absorption coefficient of light, dijIt is firefly i and fireflyThe distance between fireworm j.
Preferably, in the above-mentioned methods, the location update formula of the firefly are as follows:
Xj(t+1)=Xj(t)+βij(Xi(t)-Xj(t))+α(t)*εj；
In formula, Xi(t) and XjIt (t) is the spatial position of firefly i and firefly j in the t times iteration respectively, α is disturbanceCoefficient, εjIt is random number vector, T is the number of iterations.
Second aspect of the present invention provides a kind of mobile robot of automatic path planning characterized by comprising
Environment information acquisition module, for acquiring environmental information；
Environmental information modeling module, for being ready for path planning to mobile robot by collected environmental informationRegion modeled to construct two-dimensional plane coordinate figure, and determine the coordinate position of starting point, terminal and barrier；
Path planning module, it is logical from the path of origin-to-destination to mobile robot for being based on two-dimensional plane coordinate figureThe glowworm swarm algorithm progress path for crossing the initialization of population based on Sobol sequence and dynamic adjustment coefficient of disturbance Population Regeneration is soughtIt is excellent, thus in two-dimensional plane coordinate figure planning plan to implement into path optimizing；
Mobile drive module, the path optimizing for being completed according to planning, drives mobile robot to be moved.
Preferably, in the scheme of above-mentioned mobile robot, the path planning module is specifically included:
Basic parameter input unit for importing the basic parameter of glowworm swarm algorithm, and initializes each of glowworm swarm algorithmA basic parameter；
Sobol sequence initialization kind group unit generates popN firefly for using Sobol sequence initialization populationPosition；
Dynamic disturbances coefficient path optimizing unit obtains corresponding bright for calculating the objective function of every fireflyDegree, and select brightness maximum as optimal location；And the Attraction Degree of every firefly is calculated, by the firefly with maximum brightnessFireworm guides the movements of other fireflies, updates the position of every firefly, and recalculate the brightness of firefly；When reachingMaximum search number then exports optimum individual and stops algorithm, otherwise, recalculates the Attraction Degree of every firefly.
Preferably, in the scheme of above-mentioned mobile robot, the Sobol sequence is with 2 for base, by oneGroup direction number V1, V2, V3..., Vi..., VnIt generates, wherein Vi∈ (0,1), in Sobol sequence, the value of i-th of element jth dimensionIt can be obtained by formula:
Preferably, in the scheme of above-mentioned mobile robot, the calculating of the Attraction Degree of the firefly is publicFormula are as follows:
In formula, β0Attraction when be two firefly distances being zero, γ is the absorption coefficient of light, dijIt is firefly i and fireflyThe distance between fireworm j.
Preferably, in the scheme of above-mentioned mobile robot, the location update formula of the firefly are as follows:
Xj(t+1)=Xj(t)+βij(Xi(t)-Xj(t))+α(t)*εj；
In formula, Xi(t) and XjIt (t) is the spatial position of firefly i and firefly j in the t times iteration respectively, α is disturbanceCoefficient, εjIt is random number vector, T is the number of iterations.
Compared with prior art, the beneficial effects of the present invention are:
1, the present invention can construct two-dimensional plane coordinate figure according to collected environmental information, and initialization component is called to adoptWith Sobol sequence initialization population, dynamic disturbances coefficient update population is then based on to plan in two-dimensional plane coordinate figurePlan to implement into path, finally two-dimensional plane coordinate figure and the path planned is combined to be moved.The present invention is based on Sobol sequencesInitialization population and dynamic adjust the strategy of coefficient of disturbance, by carrying out to the key parameter in glowworm swarm algorithm-coefficient of disturbanceAdaptive adjustment overcomes the insufficient problem of existing glowworm swarm algorithm constringency performance, makes to move to enhance convergence energyMobile robot can quickly and accurately automatic path planning, improve the ability that mobile robot carries out path planning.
2, the present invention initializes firefly population using Sobol sequence, preferable sampling coverage rate can be obtained, to protectDemonstrate,prove the uniformity of initial population distribution.
Detailed description of the invention
In order to more clearly explain the embodiment of the invention or the technical proposal in the existing technology, to embodiment or will show belowThere is attached drawing needed in technical description to be briefly described, it should be apparent that, the accompanying drawings in the following description is the present inventionSome embodiments for those of ordinary skill in the art without creative efforts, can also basisThese attached drawings obtain other attached drawings.
Fig. 1 is a kind of flow chart of the automatic path planning method of mobile robot provided by the invention；
Fig. 2 is the schematic diagram of two-dimensional plane coordinate figure provided by the invention；
Fig. 3 is a kind of structural block diagram of the mobile robot of automatic path planning provided by the invention；
Fig. 4 is the structural block diagram of path planning module provided by the invention.
Specific embodiment
In order to make the object, technical scheme and advantages of the embodiment of the invention clearer, below in conjunction with the embodiment of the present inventionIn attached drawing, technical scheme in the embodiment of the invention is clearly and completely described, it is clear that described embodiment isA part of the embodiment of the present invention, instead of all the embodiments.Based on the embodiments of the present invention, those of ordinary skill in the artEvery other embodiment obtained without creative efforts, shall fall within the protection scope of the present invention.
Embodiment one
The embodiment of the present invention one provides a kind of automatic path planning method of mobile robot, right with reference to the accompanying drawingThe present embodiment is described in detail.Fig. 1 is the method flow diagram of the embodiment of the present invention one, referring to FIG. 1, the embodiment of the present inventionMethod the following steps are included:
Step S1, environmental information is acquired；
Wherein, mobile robot can obtain external environmental information by infrared sensor or the scanning of other acquisition devices.
Step S2, it is modeled by the region that collected environmental information is ready for path planning to mobile robotTo construct two-dimensional plane coordinate figure, and determine the coordinate position of starting point, terminal and barrier；
Path planning refer in the working environment for having barrier find one from origin-to-destination, bypass without collisionThe motion path (that is: finding out the collisionless shortest path from A point to B point) of all barriers.
As shown in Fig. 2, the environmental information modeling module of mobile robot can when two-dimensional plane coordinate figure constructs completionIdentify the position coordinates of barrier (such as: a, b, c) in the global area of quasi- exploration.It is more due to having from A point to the path of B pointItem, it is therefore desirable to therefrom identify shortest path using the improved glowworm swarm algorithm of the present invention.
Step S3, it is based on two-dimensional plane coordinate figure, to mobile robot from the path of origin-to-destination by being based on SobolThe initialization of population of sequence and the glowworm swarm algorithm of dynamic adjustment coefficient of disturbance Population Regeneration carry out path optimizing, thus in two dimensionIn plane coordinates figure planning plan to implement into path optimizing；
Furthermore, step S3 specifically includes the following steps:
Step S31, the basic parameter of glowworm swarm algorithm is imported, and initializes each basic parameter of glowworm swarm algorithm；
Wherein, the basic parameter may include population quantity popN, the number of iterations T, initial Attraction Degree β0, light absorption systemNumber γ, coefficient of disturbance α etc..Their initial value can be as shown in following table one:
Step S32, using Sobol sequence initialization population, the position of popN firefly is generated, calculates every fireflyObjective function to obtain corresponding brightness, and select brightness maximum as optimal location；
Specifically, the Sobol sequence is with 2 for base, by one group of direction number V1, V2, V3..., Vi ..., VnIt generates,In, Vi ∈ (0,1).Assuming that mono- group of sequence of Sobol is x1, x2, x3..., xi..., xn,Indicate i-th of element in Sobol sequenceThe value of jth dimension, can be obtained by formula:
There is sample distribution and be really distributed inconsistent, Sobol stochastic ordering in pseudo-random number sequence common at presentColumn are that ((low-discrepancy sequences) is a stable random sequence, and distribution is equal for a kind of low diversity sequenceEven property is good.The present invention initializes firefly population using Sobol sequence, preferable sampling coverage rate can be obtained, to guaranteeThe uniformity of initial population distribution.
Glowworm swarm algorithm is a kind of heuritic approach, and the algorithm simulation weaker firefly of brightness is to the stronger light of firefly of brightnessThe mobile random search of worm, usually represents target function value, i.e. f (x with the absolute brightness of firefly in glowworm swarm algorithm*)=maxx∈sF (x), which solves this optimization problem by iteration using the firefly population that quantity is popN, at the beginning of algorithmStage beginning, all fireflies are probabilistically assigned in the s of search space.xiIndicate one of i-th of firefly in the t times iterationA solution, f (xi) mean that the absolute brightness of its corresponding firefly.
Step S33, the Attraction Degree for calculating every firefly, other fireflies are guided by the firefly with maximum brightnessMovement, update the position of every firefly, and recalculate the brightness of firefly；
Every firefly has an attraction β to other fireflies, if the absolute brightness of firefly i is greater than fireflyThe absolute brightness of j, then firefly j will be attracted mobile to i by firefly i.Attraction β of the firefly i to firefly jijPublic affairsFormula is defined as:
Wherein, β0Attraction when be two firefly distances being zero, γ is the absorption coefficient of light (Light AbsorptionCoefficient), dijIt is the distance between firefly i and firefly j.
If firefly j is mobile to firefly i, then the location update formula of firefly j in the t times iteration are as follows:
Xj(t+1)=Xj(t)+βij(Xi(t)-Xj(t))+α(t)*εj (2)
In formula, Xi(t) and XjIt (t) is the spatial position of firefly i and firefly j in the t times iteration respectively, α is disturbanceCoefficient, εjIt is random number vector.
The more new formula that the present invention uses α is as follows:
From the point of view of the operation of algorithm, a biggish α value is conducive to global search, and a lesser α value is conducive to officePortion's search, therefore convergence energy is improved by carrying out dynamic adjustment to α.
Step S34, it when reaching maximum search number, then exports optimum individual and stops algorithm, otherwise, return step S33Recalculate the Attraction Degree of every firefly.
Wherein, maximum search number refers to the optimizing number of glowworm swarm algorithm, i.e. the number of iterations T.
The pseudocode of the algorithm is as follows:
Step S4, the path optimizing completed according to planning, drives mobile robot to be moved.
Wherein, the path that optimum individual is passed by is exactly optimal path, when path planning module determines an optimal pathAfterwards, mobile robot will be moved along the paths.
Method of the invention adjusts the strategy of coefficient of disturbance based on Sobol sequence initialization population and dynamic, by fireflyCoefficient of disturbance in fireworm algorithm carries out adaptive adjustment to enhance convergence energy, overcomes existing glowworm swarm algorithm and receivesThe insufficient problem for holding back performance, enables mobile robot quickly and accurately automatic path planning, improve mobile robot intoThe ability of row path planning.
Embodiment two
The embodiment of the present invention two provides a kind of mobile robot of automatic path planning, referring to FIG. 3, the present invention is realThe mobile robot for applying example includes environmental perception module 1, path planning module 2 and mobile drive module 3, wherein environment sensingModule 1 is equipped with environment information acquisition module 11 and environmental information modeling module 12, will carry out below to the function of above-mentioned module detailedThin explanation.
Environment information acquisition module 11, for acquiring environmental information.
Wherein, environment information acquisition module 11 can be set to infrared sensor or other acquisition devices, mobile robotExternal environmental information can be obtained by infrared sensor or the scanning of other acquisition devices.
Environmental information modeling module 12, for being ready for path rule to mobile robot by collected environmental informationThe region drawn is modeled to construct two-dimensional plane coordinate figure, and determines the coordinate position of starting point, terminal and barrier.
Path planning refer in the working environment for having barrier find one from origin-to-destination, bypass without collisionThe motion path (that is: finding out the collisionless shortest path from A point to B point) of all barriers.
As shown in Fig. 2, when two-dimensional plane coordinate figure constructs completion, 12 energy of environmental information modeling module of mobile robotEnough identify the position coordinates of barrier (such as: a, b, c) in the global area of quasi- exploration.It is more due to having from A point to the path of B pointItem, it is therefore desirable to therefrom identify shortest path using path planning module 2.
Path planning module 2, it is logical from the path of origin-to-destination to mobile robot for being based on two-dimensional plane coordinate figureThe glowworm swarm algorithm progress path for crossing the initialization of population based on Sobol sequence and dynamic adjustment coefficient of disturbance Population Regeneration is soughtIt is excellent, thus in two-dimensional plane coordinate figure planning plan to implement into path optimizing.
As shown in figure 4, furthermore, in the present embodiment, the path planning module 2 specifically includes:
Basic parameter input unit 21 for importing the basic parameter of glowworm swarm algorithm, and initializes glowworm swarm algorithmEach basic parameter；
Wherein, the basic parameter may include population quantity popN, the number of iterations T, initial Attraction Degree β0, light absorption systemNumber γ, coefficient of disturbance α etc..Their initial value can be as shown in following table one:
Sobol sequence initialization kind group unit 22 generates the popN light of firefly for using Sobol sequence initialization populationThe position of worm；
Specifically, the Sobol sequence is with 2 for base, by one group of direction number V1, V2, V3..., Vi ..., VnIt generates,In, Vi ∈ (0,1).Assuming that mono- group of sequence of Sobol is x1, x2, x3..., xi..., xn,Indicate i-th of element in Sobol sequenceThe value of jth dimension, can be obtained by formula:
There is sample distribution and be really distributed inconsistent, Sobol stochastic ordering in pseudo-random number sequence common at presentColumn are that ((low-discrepancy sequences) is a stable random sequence, and distribution is equal for a kind of low diversity sequenceEven property is good.The present invention initializes firefly population using Sobol sequence, preferable sampling coverage rate can be obtained, to guaranteeThe uniformity of initial population distribution.
Dynamic disturbances coefficient path optimizing unit 23 obtains corresponding for calculating the objective function of every fireflyBrightness, and select brightness maximum as optimal location；And the Attraction Degree of every firefly is calculated, by with maximum brightnessFirefly guides the movements of other fireflies, updates the position of every firefly, and recalculate the brightness of firefly；When reachingIt to maximum search number, then exports optimum individual and stops algorithm, otherwise, recalculate the Attraction Degree of every firefly.
Glowworm swarm algorithm is a kind of heuritic approach, and the algorithm simulation weaker firefly of brightness is to the stronger light of firefly of brightnessThe mobile random search of worm, usually represents target function value, i.e. f (x with the absolute brightness of firefly in glowworm swarm algorithm*)=maxx∈sF (x), which solves this optimization problem by iteration using the firefly population that quantity is popN, at the beginning of algorithmStage beginning, all fireflies are probabilistically assigned in the s of search space.xiIndicate one of i-th of firefly in the t times iterationA solution, f (xi) mean that the absolute brightness of its corresponding firefly.
Every firefly has an attraction β to other fireflies, if the absolute brightness of firefly i is greater than fireflyThe absolute brightness of j, then firefly j will be attracted mobile to i by firefly i.Attraction β of the firefly i to firefly jijPublic affairsFormula is defined as:
Wherein, β0Attraction when be two firefly distances being zero, γ is the absorption coefficient of light (Light AbsorptionCoefficient), dijIt is the distance between firefly i and firefly j.
If firefly j is mobile to firefly i, then the location update formula of firefly j in the t times iteration are as follows:
Xj(t+1)=Xj(t)+βij(Xi(t)-Xj(t))+α(t)*εj (2)
In formula, Xi(t) and XjIt (t) is the spatial position of firefly i and firefly j in the t times iteration respectively, α is disturbanceCoefficient, εjIt is random number vector.
The more new formula that the present invention uses α is as follows:
From the point of view of the operation of algorithm, a biggish α value is conducive to global search, and a lesser α value is conducive to officePortion's search, therefore convergence energy is improved by carrying out dynamic adjustment to α.
Mobile drive module 3, the path optimizing for being completed according to planning, drives mobile robot to be moved.
Wherein, the path that optimum individual is passed by is exactly optimal path, when path planning module 2 determines an optimal pathAfterwards, mobile drive module 3 will drive mobile robot to move along the paths.
Shifter people of the invention adjusts the strategy of coefficient of disturbance based on Sobol sequence initialization population and dynamic, passes throughAdaptive adjustment is carried out to enhance convergence energy to the coefficient of disturbance in glowworm swarm algorithm, existing firefly is overcome and calculatesThe insufficient problem of method constringency performance, can quickly and accurately automatic path planning, improve path planning ability.
It should be noted that a kind of mobile robot of automatic path planning provided by the above embodiment, only with above-mentioned eachThe division progress of functional module can according to need and for example, in practical application by above-mentioned function distribution by different functionEnergy module is completed, i.e., the internal structure of system is divided into different functional modules, to complete whole described above or portionDivide function.
Those of ordinary skill in the art will appreciate that implement the method for the above embodiments be can be withRelevant hardware is instructed to complete by program, the program can be stored in a computer-readable storage mediumIn, the storage medium, such as ROM/RAM, disk, CD.
The above embodiment is a preferred embodiment of the present invention, but embodiments of the present invention are not by above-described embodimentLimitation, other any changes, modifications, substitutions, combinations, simplifications made without departing from the spirit and principles of the present invention,It should be equivalent substitute mode, be included within the scope of the present invention.