Data processing: generic control systems or specific application – Generic control system – apparatus or process
Reexamination Certificate
2003-03-19
2004-11-30
Knight, Anthony (Department: 2121)
Data processing: generic control systems or specific application
Generic control system, apparatus or process
C700S245000, C700S248000
Reexamination Certificate
active
06826431
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to the field of optimal control and more particularly to distributed sensing and cooperative control systems and methods for distributed optimization.
When multiple agents or processors are controlled to cooperatively achieve an objective, the cooperative performance of the collective can be more effective than the performance of a collection of independent agents or processors. Multiple agents or processors in a collective can collect and share information to enhance each one's strategy to achieve the objective. Independent and distributed sensing and sharing of information among multiple autonomous or semi-autonomous cooperating collective members as well as cooperative control for each member of the collective can improve the search strategy to achieve the objective without sacrificing efficiency or imposing an undue communication or processing burden.
Areas that are particularly applicable are the use of multiple agents in surveillance and inspection, in following and tagging, in locating and identifying targets, and in other applications which can remove humans from tedious or potentially dangerous activities. Examples of a need for distributed optimization and cooperative control include using small autonomous robotic vehicles in the above application areas. A particular example is a search and tag operation to find the source of a time-varying chemical plume, temperature source, radiation source, or light source. Interest in the above application areas is growing due to recent advances in microelectronics and sensors. These advances include small, low power CCD cameras; small microprocessors with expanded capabilities; autonomous navigation systems using global positioning systems; and several types of small sensors; which can be used in conjunction with inexpensive, easy to fabricate, autonomous vehicles, built in quantity and cooperating in an optimal search mission.
Examples of distributed optimal searches within an n-dimensional space include cooperative software agent cyberspace searches (for example, searches using a network of interconnected computers to optimize a specified search objective, searches using the parallelization of a multiple-processor computer such as a Paragon computer, searches in a multiprocessing computer environment to find an optimal solution to a time-independent or time-dependent maximization or minimization problem), and the use of a computer to optimally solve problems such as time-varying functional surfaces and two-point boundary value problems.
Optimization Systems
Park and Vadali teach a multiple shooting method to solve trajectory optimization two-point boundary-value problems. In the multiple shooting method, a trajectory is divided into subintervals, and parameters within each subinterval are found which optimize the overall trajectory, subject to matching conditions at the boundaries between the subintervals.
Park and Vadali
do not teach cooperative utilization of information to improve and update search control strategies. See
Park and Vadali
, “Touch Points in Optimal Ascent Trajectories with First-Order State Inequality Constraints,” Journal of Guidance, Control, and Dynamics, Vol. 21, No. 4, pp. 603-610, July-August 1998.
The multiple shooting method is similar to a multilevel optimization approach where units, such as subsystems or agents, in a process are uncoupled and optimized individually, while subject to equality constraints requiring a match of certain conditions between the units. While the multilevel optimization approach works well in certain applications, it does not work where uncoupled units possess a saddle point indeterminate as a true global minimum or a local saddle point. See Avery and Foss, “A Shortcoming of the Multilevel Optimization Technique,” AlChE Journal, Vol. 17, No. 4, pp. 998-999, July 1971.
Jennings et al. teach cooperative behaviors and provision of additional force or dexterity within teams of robotic agents to accomplish a rescue task. Jennings et al. do not teach cooperative behaviors during a search task. See Jennings et al., “Cooperative Search and Rescue with a Team of Mobile Robots,” IEEE International Conference of Advanced Robotics, Monterey, Calif., 1997.
Search Control
Cooperative search applications to achieve an objective result in a need for a controller for multiple agents or processors in a collective to collect and share information to make better decisions in order to achieve the objective. Accordingly, there is an unmet need for a distributed search system suitable for multiple autonomous or semi-autonomous cooperating collective members that can be used to provide independent and distributed sensing and sharing of information as well as cooperative control for each member of the collective to improve its search strategy to achieve the objective.
SUMMARY OF THE INVENTION
The present invention provides a distributed search system suitable for controlling multiple agents to search an area for an objective utilizing a sensor, a communicator, and a cooperative controller, generating an update strategy to control each agent determined from a sensor reading and a cooperative approximation to the search area. The search area can comprise a physical geography or a cyberspace search area. Robotic vehicles, computer processors, and software agents are all suitable for use with the present invention.
The present invention teaches a new search method for controlling multiple agents or multiple processors to search an area for an objective. The objective can be any combination of the following: chemical sources, temperature sources, radiation sources, light sources, evaders, trespassers, explosive sources, time dependent sources, time independent sources, function surfaces, maximization sources, minimization sources, and optimal control of a system (for example, a communication system, an economy, a crane, a multi-processor computer). The search method utilizes sensor and location input and searches the area until an optimization condition for the objective is met.
REFERENCES:
patent: 5465525 (1995-11-01), Mifune et al.
patent: 5568030 (1996-10-01), Nishikawa et al.
patent: 6330493 (2001-12-01), Takahashi et al.
patent: 6408226 (2002-06-01), Byrne et al.
patent: 6415274 (2002-07-01), Goldsmith
patent: 6453223 (2002-09-01), Kelly et al.
patent: 6577906 (2003-06-01), Hurtado et al.
DOE Article Describing Our Cooperative Robotics Research; Apr. 1999; pp. 1-3.*
Alliance: An Architecture for Fault Tolerant, Cooperative Control of Heterogeneous Mobile Robots; Lynne Parker; Sep. 1994; pp. 776-783; IEEE journals.*
A Decentralized Cooperation Protocol for Autonomous Robotic Agents; Fang-Chang Lin et al; IEEE 1995; pp. 420-426.*
Park and Vadali, “Touch Points in Optimal Ascent Trajectories with First-Order State Inequality Constraints,” Journal of Guidance, Control, and Dynamics, vol. 21, No. 4, pp. 603-610, Jul.-Aug. 1998.
Avery and Foss, “A Shortcoming of the Multilevel Optimization Technique,” AlChE Journal, vol. 17, No. 4, pp. 998-999, Jul. 1971.
Jennings et al., “Cooperative Search and Rescue with a Team of Mobile Robots,” IEEE International Conference on Advanced Robotics, Monterey, CA, 1997.
Lewis et al., “Cooperative Control of a Squad of Mobile Vehicles,” IASTED International Conference on Control and Applications, Honolulu, HI, Aug. 12-14, 1998.
Hurtado et al., “Distributed Sensing and Cooperative Control for Swarms of Robotic Vehicles,” Proceedings of IASTED International Conference on Control and Applications, pp. 175-178, Honolulu, HI, Aug. 12-14, 1998.
Dohrmann Clark R.
Hurtado John E.
Robinett, III Rush D.
Conley William R.
Hartman Jr. Ronald D
Knight Anthony
Libman George H.
Sandia Corporation
LandOfFree
Distributed optimization system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed optimization system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed optimization system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3338396