Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Improved ant colony path planning algorithm based on non-uniform modeling

A path planning and non-uniform technology, applied in the direction of calculation, calculation model, biological model, etc., can solve the problem of not being able to escape the deadlock state

Active Publication Date: 2019-03-22
HARBIN INST OF TECH AT WEIHAI
View PDF3 Cites 24 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

This approach reduces the probability of selecting a deadlock grid in the previous grid, but if there is only 1 optional grid (such as Figure 8 shown), this approach does not escape the deadlock state

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Improved ant colony path planning algorithm based on non-uniform modeling
  • Improved ant colony path planning algorithm based on non-uniform modeling
  • Improved ant colony path planning algorithm based on non-uniform modeling

Examples

Experimental program
Comparison scheme
Effect test

Embodiment

[0156] On a computer with Windows 10 operating system, Intel Core i5-5250U CPU, and a main frequency of 1.6GHz, the algorithm is verified on the platform of Matlab R2014b. The values ​​of the parameters in the algorithm are as follows: τ=15, γ=2, α=2, β=1, q 0 =0.6, δ=0.2, ρ=1, Δτ o =0, σ=5, Q=200, μ 1 =0.3,μ 2 =0.3,μ 3 = 0.4, c p =100,Q o =100,τ max =0.4,τ min =0.0001, ρ=1, c=3, v=5m / s, D safe = 5km, r min = 0.01 km. The ant population contains 30 ants, and the maximum number of iterations is set to 60.

[0157] (1) Comparison of non-uniform grid model and uniform grid model

[0158] The present invention uses quadtree modeling to obtain a non-uniform grid model in order to verify the validity of the non-uniform grid model. The non-uniform modeling method and the uniform modeling method are used to model the same search space (sea area of ​​56.6km×52.7km), and the minimum grid scale is set to be the same (shortest length and width>=0.01km), and then the improved a...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to the technical field of route planning methods, in particular to an improved ant colony path planning algorithm based on non-uniform modeling. The improved ant colony path planning algorithm considers the shortcomings of a uniform modeling scheme to modeling in a complex environment, and quadtree modeling is proposed to obtain a non-uniform grid model; the improved ant colony path planning algorithm based on a non-uniform grid model is provided, the non-uniform grid model is used as a basis for improving a basic ant colony algorithm, the distance between a node and an obstacle is considered during selection of a path point, and the distance between a node to be selected and the obstacle is considered during the selection of the path point; an 'ant-cycle' pheromone update way is adopted, and the pheromone size is limited when the global pheromone is updated; a simulation experiment shows that the non-uniform grid model is superior to a uniform grid model, and theimproved ant colony algorithm is faster in convergence rate and can get a path which better meets the needs of underwater vehicles in the complex environments compared with other basic ant colony algorithms.

Description

Technical field: [0001] The present invention relates to the technical field of path planning methods, specifically, it is an improved basic ant colony algorithm based on a non-uniform grid model, which can obtain a more complex An improved ant colony path planning algorithm based on non-uniform modeling of paths required by underwater vehicles in the environment. Background technique: [0002] Underwater vehicle path planning refers to planning a safe, collision-free path that satisfies the optimization goal in the underwater environment after the starting point and the target point are given. The path planning algorithm is often divided into three steps. The first step is environment modeling, the second step is to use the algorithm to plan the path based on the environment model, and the third step is path optimization. In previous studies, evenly partitioned modeling schemes were often used for environment modeling, such as grid method and polar coordinate modeling meth...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G01C21/20G06N3/00
CPCG06N3/006G01C21/20
Inventor 张永健徐阳帆
Owner HARBIN INST OF TECH AT WEIHAI
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products