Discovery and monitoring of an environment using a plurality of robots

Patent metadata

Field	Value
Publication number	US-9606542-B2
Application number	US-201213348846-A
Country	US
Kind code	B2
Filing date	Jan 12, 2012
Priority date	Jan 12, 2012
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

Techniques are provided for discovery and monitoring of an environment using a plurality of robots. A plurality of robots navigate an environment by determining a navigation buffer for each of the robots; and allowing each of the robots to navigate within the environment while maintaining a substantially minimum distance from other robots, wherein the substantially minimum distance corresponds to the navigation buffer, and wherein a size of each of the navigation buffers is reduced over time based on a percentage of the environment that remains to be navigated. The robots can also navigate an environment by obtaining a discretization of the environment to a plurality of discrete regions; and determining a next unvisited discrete region for one of the plurality of robots to explore in the exemplary environment using a breadth-first search. The plurality of discrete regions can be, for example, a plurality of real or virtual tiles.

First claim

What is claimed is:

1. A robot apparatus for navigating in an environment, comprising:
a memory; and
at least one processing device, coupled to the memory, operative to:
obtain a discretization of said environment to a plurality of discrete regions;
determine, using one or more of said at least one processing device of said robot apparatus, a next unvisited discrete region in said environment for said robot apparatus to explore in said exemplary environment using one or more of a breadth-first search and a depth-first search;
determine, using one or more of said at least one processing device of said robot apparatus, if at least a second robot encounters a conflict with a path in said environment of said robot apparatus to said next unvisited discrete region in said environment by processing one or more trees generated by said one or more of said breadth-first search and said depth-first search of said second robot; and
in response to said conflict detected by processing said one or more trees, generate, using one or more of said at least one processing device of said robot apparatus, one or more of at least one new breadth-first search tree and at least one new depth-first search tree for at least one of said robot apparatus and said second robot,
wherein at least one of said robot apparatus and said second robot navigates within said environment using one or more of said at least one new breadth-first search tree and said at least one new depth-first search tree.

2. The robot apparatus of claim 1 , wherein said environment comprises a known environment.

3. The robot apparatus of claim 1 , wherein said determination of said next unvisited discrete region in said environment further comprises each robot in a plurality of robots taking a hypothetical step into one of said discrete regions at a time in all possible directions, and maintaining a breath-first search tree of paths until one robot reaches said next unvisited discrete region.

4. The apparatus of claim 1 , wherein said conflict comprises one or more of (i) said robot apparatus and said second robot are at a same discrete region at a same time, and (ii) given two discrete regions t and s, one of said robot apparatus and said second robot went from discrete region t to discrete region s while the other of said robot apparatus and said second robot went from discrete region s to discrete region t.

5. An article of manufacture for navigating a robot apparatus in an environment, comprising a tangible machine readable recordable medium containing one or more programs which when executed implement the steps of:
obtaining a discretization of said environment to a plurality of discrete regions;
determining, using one or more of said at least one processing device of said robot apparatus, a next unvisited discrete region in said environment for said robot apparatus to explore in said exemplary environment using one or more of a breadth-first search and a depth-first search;
determining, using one or more of said at least one processing device of said robot apparatus, if at least a second robot encounters a conflict with a path in said environment of said robot apparatus to said next unvisited discrete region in said environment by processing one or more trees generated by said one or more of said breadth-first search and said depth-first search of said second robot; and
in response to said conflict detected by processing said one or more trees, generate, using one or more of said at least one processing device of said robot apparatus, one or more of at least one new breadth-first search tree and at least one new depth-first search tree for at least one of said robot apparatus and said second robot,
wherein at least one of said robot apparatus and said second robot navigates within said environment using one or more of said at least one new breadth-first search tree and said at least one new depth-first search tree.

6. The article of manufacture of claim 5 , wherein said plurality of discrete regions comprise a plurality of real or virtual tiles.

7. The article of manufacture of claim 5 , wherein said environment comprises a known environment.

8. The article of manufacture of claim 5 , wherein said step of determining a next unvisited discrete region in said environment further comprises the steps of each robot in a plurality of robots taking a hypothetical step into one of said discrete regions at a time in all possible directions, and maintaining a breath-first search tree of paths until one robot reaches said next unvisited discrete region in said environment.

9. The article of manufacture of claim 8 , wherein said determining step further comprises the steps of said robot apparatus declaring to others of the plurality of robots that said robot apparatus has reached said next unvisited discrete region in said environment in said breath-first search tree; said others of said plurality of robots determining if there is a conflict with said robot apparatus; and said robot apparatus collapsing said breadth-first search tree to a single point of said next unvisited discrete region in said environment.

10. The article of manufacture of claim 5 , wherein said conflict comprises one or more of (i) said robot apparatus and said second robot are at a same discrete region at a same time, and (ii) given two discrete regions t and s, one of said robot apparatus and said second robot went from discrete region t to discrete region s while the other of said robot apparatus and said second robot went from discrete region s to discrete region t.

Assignees

• Guo Shang Q
• Isci Canturk
• Lenchner Jonathan
• Mukherjee Maharaj
• IBM

Inventors

• Guo Shang Q
• Isci Canturk
• Lenchner Jonathan
• Mukherjee Maharaj

Classifications

• G05B2219/39146

  Swarm, multiagent, distributed multitask fusion, cooperation multi robots · CPC title

• G05D1/0291 Primary

  Fleet control (monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127) · CPC title

• G05B19/41815

  characterised by the cooperation between machine tools, manipulators and conveyor or other workpiece supply system, workcell · CPC title

• G08G1/20

  Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles · CPC title

• G05B2219/39168

  Multiple robots searching an object · CPC title