-
Notifications
You must be signed in to change notification settings - Fork 20
Algorithms
Other algorithm guides: Area Coverage | Defense Algorithms
Agents can be instructed to perform algorithms either alone or as part of a team. These are initialized using defined Madara variables read by the Controller. Algorithms are defined by an algorithm and some variable number of parameters. Two basic types of algorithms will be discussed, Area Coverage and Formation. The algorithm keys are all prefixed by "agent.{.id}.", so for agent 1 the keys would be "agent.1.algorithm".
During algorithm initialization, a set of algorithm status variables are created in the knowledge base. These are of
the form agent.{.id}.algorithm.<algorithm_name>. {.id} is the id of the device running the algorithm.
<algorithm_name> is the algorithm that the device is executing. The <algorithm_name> is the all lower case version
of the name of each algorithm. The <algorithm_name> for area coverage algorithms is listed next to each algorithms
name and is a shortened form of the full algorithm.
Area Coverage algorithms instruct a group of drones to surveil a region or search area. The behavior can determined by a random distribution, sensor data from the swarm, or precomputed before beginning the coverage. More information about these algorithms is on the Area Coverage page.
The formation algorithm allows any static formation to be defined and used by a group of agents.
| Key | Value |
|---|---|
| algorithm | "formation" |
| algorithm.args.head | lead agent id |
| algorithm.args.offset | offset |
| algorithm.args.destination | destination |
| algorithm.args.group | group name |
The formation algorithm is initialized by the "formation" algorithm and requires four arguments. The first argument is the id of the "lead" agent of the formation. This agent is the common reference point for the next argument.
The second argument is the relative location of this agent in the formation. This parameter is a
double vector of values ( [rho,phi,z] ) in the cylindrical coordinate
system with the location of the lead agent as the origin. rho is the planar distance
from the lead. phi is the angular offset in radians from forward of the lead agent with
positive phi being to the right and negative phi to the left. z is the altitude offset. For
example [3,1.57,4] would be the position three meters to the right of and four meters above the
lead agent. The lead agent is at [0,0,0], but it will ignore this value regardless. If z is
missing, then it is defaulted to 0.
The third argument is the destination of the formation. This allows formation members to determine the forward direction of the lead agent and thus their expected absolute position. It is assumed the formation will stay at the same altitude at which it starts. This is also a double vector.
The fourth argument is the list of agents involved in the formation as an integer vector. For example, if agents 4, 2, 6, 3, and 8 are involved in the formation, then the parameter should be [4,2,6,3,8].
The follow algorithm has an agent follow another agent with a known position.
| Key | Value |
|---|---|
| algorithm | "follow" |
| algorithm.args.target | target id |
| algorithm.args.delay | delay |
The follow algorithm is called with the "follow" algorithm. It takes two arguments. The first is the
id of the target to follow. This is used to key on the agent.{target}.location variable in the
knowledge base. The second argument is the delay. The agent will be delay timesteps behind the
target agent.
The KaRL algorithm evaluates or waits on MADARA knowledge base information. This algorithm can be useful for initializing knowledge for other algorithms and can also be useful for passive monitoring on other agents who are waiting for conditions to be true or false before starting their own mission.
| Key | Value |
|---|---|
| algorithm | "karl" |
| algorithm.args.logic | the KaRL logic to evaluate |
| algorithm.args.store_result | store result of evaluation into another variable |
| algorithm.args.wait_time | time to wait for evaluation to be non-true |
logic is stated in KaRL, a real-time scripting language made available in MADARA (http://madara.ai/).
store_result is a convenience argument to allow for wrapping the logic in another variable assignment. For instance,
if store_result is "result" and logic is set to 40 * 25 then this would be the equivalent of making a logic of
result = 40 * 25. Wait_time is the time, in seconds, that the algorithm should wait and re-execute until the result
of the logic evaluation is non-zero. If the logic will never be non-zero, then the logic will be evaluated for the
full wait_time. A negative wait_time indicates the algorithm should wait forever for the logic to evaluate non-zero.
The move algorithm has an agent move to a series of locations. This is like Waypoint coverage but without any attempt to track coverage information. Additionally, Move can specify repeat to indicate repetition of the locations sequence.
| Key | Value |
|---|---|
| algorithm | "waypoints" or "move" |
| algorithm.args.repeat | number of times to repeat locations sequence |
| algorithm.args.locations.size | number of locations |
| algorithm.args.locations.0 | first location to visit |
| algorithm.args.locations.N | Nth location to visit |
repeat of 0 or 1 is always 1 sequence. 2+ will be 2 or more repetitions. A negative value for repeat means to repeat forever or until the user changes the algorithm.
| Key | Value |
|---|---|
| algorithm | "patrol" or "ppac" |
| algorithm.args.area | region to patrol |
| algorithm.args.time | maximum time in seconds to patrol (negative is infinite time) |
| algorithm.args.counter | if set, patrols counter clockwise |
Each agent creates a convex hull around a region or search area composed of one or more regions. The agent chooses the closest vertex in the convex hull and then moves around the area in either a clockwise or counterclockwise manner. Time can be set to a number of seconds to spend patrolling the region. A negative value for time means the agent will patrol forever or until its algorithm is changed by a user.
The wait algorithm does nothing, but returns a FINISHED status after a period of time has passed.
| Key | Value |
|---|---|
| algorithm | "wait" |
| algorithm.args.time | time in seconds |
The formation sync algorithm attempts to move a swarm or group formation using a synchronous model of computation. Basically, no swarm member will move out of current position until the formation itself is ready to move to the next location. Unlike most other algorithms, formation sync is meant to be used as a swarm.algorithm or as a agent.0.algorithm that identifies a group of devices to use.
| Key | Value |
|---|---|
| algorithm | "formation sync" |
The arguments to Formation Sync are specified using the "algorithm.args" prefix.
| Arg n | Value n + 1 | Required | Default | Description |
|---|---|---|---|---|
| start | double[2-3] | Yes | N/A | Starting GPS location of formation |
| end | double[2-3] | Yes | N/A | Ending GPS location of formation |
| formation | string | No. Default | LINE | LINE, CIRCLE, RECTANGLE, PYRAMID |
| buffer | double | No. Default | 5.0 | Distance between members in meters |
| group | string | No. Default | All devices | name in group.{name}.members |
| barrier | string | No. Default | barrier.fs | name of vector to use for syncing |
The start and end are the only required arguments that must be passed. Everything else has a default value that should be okay for at least the first Formation_Sync call. The only formation currently supported is LINE, so there is no reason to change this to the other formations yet. Buffer is the distance in meters between formation members. The other variables are slightly less intuitive and will be described now.
Group is the name of a group that has already been defined in the knowledge base. To define a group, simply create a MADARA String_Vector container that points to a location in the knowledge base with the prefix "group." and the postfix "members". So, if you wanted to define a group called "seekers", then you would create a String_Vector that pointed to "group.seekers.members". You would then add the seekers members to the String_Vector and send this out to all of the devices that would need to participate in the formation (at the least). The group listing does not have to be in any kind of order, but the order the group listing is specified will determine the position of the device in the formation.
Example group seekers in Knowledge Base
| Var | Value |
|---|---|
| group.seekers.members.size | 4 |
| group.seekers.members.0 | agent.0 |
| group.seekers.members.1 | agent.3 |
| group.seekers.members.2 | agent.2 |
| group.seekers.members.3 | agent.10 |
A barrier is a logical boundary in the execution of a distributed program that prevents processes participating in the barrier from proceeding out of sync with the rest of the participants. A barrier is sort of like a referee at a race who prevents anyone from starting the race until everyone is at the starting line and ready to go.
The barrier argument is a unique location in the knowledge base that will be used for the Formation Sync algorithm. It should be unique per algorithm that you issue. By default, this points to barrier.formation_sync in the Knowledge_Base. However, if you issue another algorithm before resetting all knowledge bases, you should set barrier on subsequent runs to a different location (e.g., barrier.formation_sync.2, barrier.formation_sync.3).
The Executor algorithm executes a list of other algorithms in sequence. The Executor features several quality-of-service parameters that augment how these algorithms are executed.
The repeat parameter specifies how many times the sequence should be executed. Zero is the default but this has the same effect as specifying 1. A negative repeat tells the Executor algorithm to loop forever or until a new algorithm replaces the Executor.
The max_time parameter can be specified per algorithm to dictate the maximum allowable time for an algorithm to execute. Units of max_time are in seconds, but it is considered a double so fractional seconds (e.g. 2.5) are perfectly acceptable.
Another qos parameter is precondition. Precondition specifies that the algorithm should not be launched until an indicated MADARA KaRL conditional evaluates to true (non-zero).
To use Executor, determine the number of algorithms you plan to sequence and set the algorithm.args.size field appropriately. Then, new algorithms are specified via an index and .algorithm. See the example below which waits on a KaRL expression for longer than the Executor is willing to let it run. This showcases all of the major qos properties used in a sequence of 3 algorithms.
// main algorithm is the Executor algorithm
agent.0.algorithm="executor";
// there will be three algorithms
agent.0.algorithm.args.size = 3;
// Executor should execute the sequence twice
agent.0.algorithm.args.repeat = 2;
/**
* algorithm zero is KaRL with a logic of "count = 0" and then always return zero.
* KaRL will try to wait for 120s but the Executor will stop it at 15s
**/
agent.0.algorithm.args.0.algorithm = "karl";
agent.0.algorithm.args.0.algorithm.args.logic = "count = 0 ;> 0";
agent.0.algorithm.args.0.algorithm.args.wait = 120.0;
agent.0.algorithm.args.0.algorithm.max_time = 15.0;
/**
* algorithm one is KaRL with a logic of "++count" called every execute.
* KaRL will try to wait for 120s but the Executor will stop it at 60s.
* Depending on the controller hertz rate, the count could be 60 at 1hz
* or 120 at 2hz, etc.
**/
agent.0.algorithm.args.1.algorithm = "karl";
agent.0.algorithm.args.1.algorithm.args.logic = "++count ;> 0";
agent.0.algorithm.args.1.algorithm.args.wait = 120.0;
agent.0.algorithm.args.1.algorithm.max_time = 60.0;
/**
* algorithm two is KaRL with a logic of "++count" called every execute.
* KaRL will try to wait for 120s but the Executor will stop it at 15s.
* The algorithm has a somewhat arbitrary precondition of count being
* greater than 15. Algorithm 2 would block indefinitely or until you
* change count to 16+ via another agent if algorithm 1 had not set
* count appropriately. This is useful when you want to execute a sequence
* up to a point and then have everything wait for a human user or other
* agents to be ready.
**/
agent.0.algorithm.args.2.precond = "count > 15";
agent.0.algorithm.args.2.algorithm = "karl";
agent.0.algorithm.args.2.algorithm.args.logic = "++count ;> 0";
agent.0.algorithm.args.2.algorithm.args.wait = 120.0;
agent.0.algorithm.args.2.algorithm.max_time = 15.0;