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

Hop searching based conflict-avoiding path planning method for multiple robots

A path planning and conflict avoidance technology, which is applied to instruments, motor vehicles, vehicle position/route/height control, etc., can solve the problems of low efficiency of system planning conflict-free paths and high time complexity of search algorithms

Active Publication Date: 2019-01-01
HARBIN ENG UNIV
View PDF4 Cites 41 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0005] The purpose of the present invention is to provide a path planning method for multi-robot conflict avoidance based on hop search, which can solve the problems of high time complexity of multi-agent conflict avoidance search algorithm and low efficiency of system planning conflict-free paths

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
  • Hop searching based conflict-avoiding path planning method for multiple robots
  • Hop searching based conflict-avoiding path planning method for multiple robots
  • Hop searching based conflict-avoiding path planning method for multiple robots

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0061] The present invention will be further described below in conjunction with accompanying drawing:

[0062] The multi-agent conflict avoidance path planning method based on JPS (Jump point search) aims to solve the problems of high time complexity of multi-agent conflict avoidance search algorithm and low efficiency of system planning conflict-free path. The main idea is to use the CBS (Conflict-based Search) search framework and the underlying jump-point search algorithm to quickly and accurately plan conflict-free paths for multiple agents based on the input map scene information, and finally output the sum of the path times of all agents The smallest optimal path.

[0063] The above-mentioned CBS-based search algorithm is mainly divided into two-layer search algorithms, including the bottom-level search algorithm and the top-level search algorithm. The bottom-level search algorithm refers to the path sequence result of planning a single agent, which can effectively redu...

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 belongs to the field of artificial intelligence and particularly relates to a hop searching based conflict-avoiding path planning method for multiple robots. The method specifically comprises the following steps: 1. preprocessing a map into a data map; 2. carrying out path planning on all agents by using a searching framework of CBS, i.e., Conflict-based Search and using an unconstrained hop searching algorithm; 3. traversing a multiway tree to carry out conflict detection, constraint increasing and constrained path planning on all the agents. According to the hop searching basedconflict-avoiding path planning searching algorithm, provided by the invention, through greatly reducing the quantity of expanding nodes during path planning, the efficiency of searching of conflict-free path sequence algorithms of all the agents planned by a system is increased; during path re-searching in conflict processing, real distance from a current node to an end point is directly searched through an EfftiveG table, thus, the time for planning conflict-free path sequences of all the agents by the system is shortened again, and the searched shortest path can be closer to a real path.

Description

technical field [0001] The invention belongs to the field of artificial intelligence, and in particular relates to a path planning method for multi-robot conflict avoidance based on jump point search. Background technique [0002] At present, multi-robots are widely used in many fields, such as: logistics storage, search and rescue, mine exploration, mine clearance and various other dangerous or boring tasks, in which the robot not only needs to bypass some Obstacle areas, and it is necessary to ensure that no collisions between robots occur. According to the existing literature, each robot can be regarded as an agent, and quickly planning a conflict-free optimal path for multiple robots is a multi-agent path planning problem. [0003] When there is only one agent, the problem can usually use A* algorithm, Dijkstra algorithm, Floyed algorithm and other algorithms to quickly plan the optimal path. But when there are multiple agents, there will be a problem of multi-agent re...

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/20
CPCG01C21/20G05D1/0289
Inventor 冯光升庄晓晓李滕付俊强潮洛蒙吕宏武
Owner HARBIN ENG UNIV
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

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com