Distributed optimization system and method
First Claim
1. A method for controlling a plurality of agents to search an area for an objective, wherein each agent comprises a sensor, a communicator, and a cooperative controller, the method comprising on each agent:
- a) determining a reading from the sensor;
b) sharing the reading with other agents in the plurality of agents;
c) concurrently approximating the search area, according to a plurality of readings from the plurality of agents;
d) solving for a cooperative approximation, corresponding to the concurrently approximated search area;
e) updating an agent control strategy, according to the cooperative approximation and the reading; and
f) repeating steps a) through e) until an optimization condition for the objective is met.
3 Assignments
0 Petitions
Accused Products
Abstract
A search system and method for controlling multiple agents to optimize an objective using distributed sensing and cooperative control. The search agent can be one or more physical agents, such as a robot, and can be software agents for searching cyberspace. The objective can be: chemical sources, temperature sources, radiation sources, light sources, evaders, trespassers, explosive sources, time dependent sources, time independent sources, function surfaces, maximization points, minimization points, and optimal control of a system such as a communication system, an economy, a crane, and a multi-processor computer.
49 Citations
11 Claims
-
1. A method for controlling a plurality of agents to search an area for an objective, wherein each agent comprises a sensor, a communicator, and a cooperative controller, the method comprising on each agent:
-
a) determining a reading from the sensor;
b) sharing the reading with other agents in the plurality of agents;
c) concurrently approximating the search area, according to a plurality of readings from the plurality of agents;
d) solving for a cooperative approximation, corresponding to the concurrently approximated search area;
e) updating an agent control strategy, according to the cooperative approximation and the reading; and
f) repeating steps a) through e) until an optimization condition for the objective is met. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
a) a location for the agent; and
b) a measurement of the search area at the location.
-
-
3. The method of claim 1, wherein the cooperative controller comprises step memory.
-
4. The method of claim 1, wherein sharing the reading comprises communicating the reading to each agent in the plurality of agents.
-
5. The method of claim 1, wherein each agent further comprises an agent communication range, wherein sharing the reading comprises communicating the reading to a plurality of nearest neighbor agents in the plurality of agents within the communication range of the agent.
-
6. The method of claim 1, wherein the cooperative approximation corresponds to a quadratic form according to:
-
where xi and xj denote points in an N dimensional search space, and aq for every q=0, 1, . . . , ½
N(N+3) denotes unknown coefficients defining the quadratic form at time t.
-
-
7. The method of claim 6, wherein solving for a cooperative approximation comprises solving for the unknown coefficients using a least squares approximation.
-
8. The method of claim 1, wherein the objective is selected from the group consisting of:
- chemical sources, temperature sources, radiation sources, light sources, evaders, trespassers, intruders, explosive sources, and combinations thereof.
-
9. The method of claim 1, wherein the objective is selected from the group consisting of:
- function surfaces, maximization points, minimization points, optimal control of a system, and combinations therof.
-
10. A method for controlling a plurality of processors in a computer to cooperatively optimize an objective for a surface function, the method comprising on each processor:
-
a) evaluating the surface function at a location;
b) sharing the evaluation and the location with other processors in the plurality of processors;
c) concurrently approximating the surface function, according to evaluations and locations from the plurality of processors;
d) solving for a cooperative approximation, corresponding to the concurrently approximated surface function;
e) updating a processor control strategy, according to the cooperative approximation and the location; and
f) repeating steps a) through e) until an optimization condition for the objective is met. - View Dependent Claims (11)
where xi and xj denote points in an N dimensional search space, and aq for every q=0, 1, . . . , ½
N(N+3) denotes unknown coefficients defining the quadratic form at time t.
-
Specification