Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
1999-06-24
2002-07-02
Black, Thomas (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
C706S016000, C706S017000
Reexamination Certificate
active
06415274
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to the field of coordinating multiple agents in collective searching, specifically coordinating mobile robots for collective searching.
Many challenging applications in robotics involve distributed searching and sensing by a team of robots. Examples include mapping minefields, extraterrestrial and undersea exploration, volcano exploration, location of chemical and biological weapons, and location of explosive devices. In general, such applications can involve rough terrain including obstacles, non-stationary and dilute search goals, deliberate interference with the searchers, and limited opportunities for human interaction with the searchers. Limited human intervention makes teleoperation problematic, and suggests a need for decentralized coordination schemes which feature collective decision-making by individual autonomous robots. Cost considerations when applied to large groups of searchers suggest a need for distributed coordination that uses shared data to overcome limited sensor precision.
Designing a robot team to search a sensate region for a specific target phenomenon involves numerous engineering tradeoffs among robot attributes and environmental variables. For example, battery-powered robots have a finite energy store and can search only a limited area before depleting it. Success in finding a target source with finite energy resources can also depend on other characteristics of the robot such as sensor accuracy and noise, and efficiency of the locomotive subsystem, and well as properties of the collective search such as the number of robots in the team, the use of shared information to reduce redundant search, and the team coordination strategy used to ensure a coherent search process.
Numerous team coordination strategies have been proposed. See, e.g., Cao et al. “Cooperative Mobile Robotics: Antecedents and Directions”, Proceedings of IEEE/RSJ IROS (1995). Strategies for cooperative action encompass theories from such diverse disciplines as artificial intelligence, game theory and economics, theoretical biology, distributed computing and control, animal ethology, and artificial life. For example, Reynolds simulated the formation of flocks, herds, and schools in which multiple autonomous agents were driven away from obstacles and each other by inverse square law repulsive forces. See Reynolds “Flocks, Herds, and Schools”, Computer Graphics, Volume 21 No. 4, pp. 25-34 (1987). Part of the motivation behind Reynolds' work is the impression of centralized control exhibited by actual bird flocks, animal herds, and fish schools, despite the fact that each agent (bird, animal, or fish) is responding only to its limited range local perception of the world.
Most current coordination strategies do not include a formal development of the system dynamics. See, e.g., Brooks “Intelligence Without Reason”, Proceedings IJCAO-91 (1991); Misawa “Discrete-Time Sliding Mode Control: the Linear Case”, Journal of Dynamic Systems, Measurement, and Control, Volume 119 (1997). Consequently, important system properties such as stability, reachability, observability, and robustness cannot be characterized. Many of the schemes rely on stable controls at a lower level and provide coordination at a higher level. The coordination is often heuristic and ad hoc.
Appropriate coordination strategies can be used in applications beyond teams of physical robots. For example, autonomous software agents, properly coordinated, can search information or trends in cyberspace or other electronic storage.
Accordingly, there is a need for a coordination method that can use shared information to reduce energy expended, compensate for noisy or deliberately misleading sensors, and allow robust collective searching.
SUMMARY OF THE INVENTION
The present invention comprises a decentralized coordination strategy called alpha-beta coordination that can use shared information to reduce energy expended, compensate for noisy or deliberately misleading sensors, and allow robust collective searching. The alpha-beta coordination strategy is a family of collective search methods that allow teams of communicating agents to implicitly coordinate their search activities through a division of labor based on self-selected roles and self-determined status. An agent can play one of two complementary roles. An agent in the alpha role is motivated to improve its status by exploring new regions of the search space. An agent in the beta role is also motivated to improve its status, but is conservative and tends to remain aggregated with other agents until alpha agents have clearly identified and communicated better regions of the search space. An agent can select its role dynamically based on its current status value relative to the status values of neighboring team members. Status can be determined by a function of the agent's sensor readings, and can generally be a measurement of source intensity at the agent's current location. An agent's decision cycle can comprise three sequential decision rules: (1) selection of a current role based on the evaluation of the current status data, (2) selection of a specific subset of the current data, and (3) determination of the next heading using the selected data. Variations of the decision rules produce different versions of alpha and beta behaviors that lead to different collective behavior properties.
Advantages and novel features will become apparent to those skilled in the art upon examination of the following description or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
REFERENCES:
patent: 5388189 (1995-02-01), Kung
patent: 5778150 (1998-07-01), Chan et al.
patent: 5832467 (1998-11-01), Wavish
patent: 5896297 (1999-04-01), Valerino, Sr.
patent: 5970482 (1999-10-01), Pham et al.
patent: 6021403 (2000-02-01), Horvitz et al.
patent: 6122572 (2000-09-01), Yavnai
patent: 6247002 (2001-06-01), Sreels
Mobile networking in the Internet, Charles E. Perkins, ACM (1998) Mobile Networks and Application 3 (1998) pp. 319-334.*
Experiences with network-based user agents for mobile applications, Thomas F. La Porta, Ranachandran Ramjee, Thomas Woo, Krishan K. Sabnani, ACM (1998) Mobile Networks and Applications 3 (1998) pp. 123-141.*
Strategies for Distributed Search, Michael A. Bauer, Tong Wang, ACM (1992) 089791-472-4/92/0002/0251.*
Managed File Distribution on the Universe Network, Christopher S. Cooper, ACM (1984) 0-89791-136-9/84/006/0010.*
Active mobile robot localization by entropy minimization, Burgard, W., Fox, D., Thrun, S., Advanced Mobile Robots, 1997, Proceedings., Second EUROMICRO workshop on, 1997 pp. 155-162.*
Stochastic prediction of human motion and control of robots in the service of human Tadokoro, S.; Ishikawa Y.; Takebe, T.; Takamori, T. Systems, Man and Cybernetics, 1993. ‘Systems Engineering in the Service of Humans’, 1993 pp. 503-508 vol. 1.*
Early Power Exploration—A World Wide Web Application, David Lidsky, Jan M. Rabaey, 33rdDesign Automation Conference, ACM (1996) 0-89791-833-9/96/0006.*
SPIE Proceeding vol. 1831, Mobile Robots VII, Editor(s) William J. Wolfe, Univeristy of Colorado/Denver, Littleton, CO, USA;Wendell H. Chun, Martin Marietta Astronautics Group, Denver, CO, USA. ISBN: 0-8194-1032-2, Nov. 20, 1992, Boston MA, USA.*
SPIE Proceeding vol. 3523, Sensor Fusion and Decentralized Control in Robotics Systems, Editor(s): Paul S. Schenker, Jet Propulsion Lab., Pasadena, CA, USA; Gerald T. McKee, University of Reading, Reading, United Kingdom.ISBN: 0-8194-2984-8, Nov. 6, 1998.*
Self-Organization in Large Populations of Mobile Robots, Cem Unsal, Thesis, Master of Science in Electrical Ingineering, Virginia Polytechnic Institute and State University, May 1993, Blacksburg, Virginia.*
Sensor Models for AHS Simulations, Cem Unsal, Feb. 1998, The Robotics Institute, Carnegie Mellon University, Pittsburgh, Pennsylvania.*
Human Driver Models
Black Thomas
Grafe V. Gerald
Holmes Michael B.
Sandia Corporation
LandOfFree
Alpha-beta coordination method for collective search does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Alpha-beta coordination method for collective search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alpha-beta coordination method for collective search will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2882597