Algorithms

Prerequisites

MADARA

---

Introduction

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 a command and some variable number of parameters. Two basic types of algorithms will be discussed, Area Coverage and Formation. The command keys are all prefixed by "agent.{.id}.", so for agent 1 the keys would be "agent.1.command".

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

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.

---

Formation

The formation algorithm allows any static formation to be defined and used by a group of agents.

Key	Value
command	"formation"
command.0	lead agent id
command.1	offset
command.2	destination
command.3	member list

The formation algorithm is initialized by the "formation" command 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].

---

Follow Algorithm

The follow algorithm has an agent follow another agent with a known position.

Key	Value
command	"follow"
command.0	target id
command.1	delay

The follow algorithm is called with the "follow" command. 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.

---

Move Algorithm

The move algorithm has an agent move to a new location.

Key	Value
command	"move"
command.0	location

---

Wait Algorithm

The wait algorithm does nothing, but returns a FINISHED status after a period of time has passed.

Key	Value
command	"wait"
command.0	time in seconds

---

Formation Sync Algorithm

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.command or as a agent.0.command that identifies a group of devices to use.

Key	Value
command	"formation sync"

The arguments to Formation Sync are done in pairs in the argument listing and any order of pairings is allowed, so long as the pairs are not broken up.

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 command that you issue. By default, this points to barrier.formation_sync in the Knowledge_Base. However, if you issue another command 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).

---

Executive Algorithm

The Executive algorithm is a queue of other algorithms to run.

Key	Value
command	"executive"
command.0	algorithm 0
command.1	args for algorithm 0
...	...
command.2n - 2	algorithm n
command.2n - 1	args for algorithm n

The Executive algorithm is a way to set a series of commands for an agent to execute. This can be useful if agents need to travel outside of network communications range and a single algorithm will not accomplish all the work that the agent needs to do while disconnected. Below is an example.

Key	Value
command	"executive"
command.0	"move"
command.1	"move_args_0"
command.2	"wait"
command.3	"wait_args"
command.4	"urec"
command.5	"urec_args_0"
command.6	"wait"
command.7	"wait_args"
command.8	"move"
command.9	"move_args_1"

The even numbered command args (0,2,4,...) are the algorithms to run while the odd numbered command args (1,3,5,...) are the arguments to those algorithms. In this case "move_args_0", "wait_args", "urec_args_0", and "move_args_1" need to be populated.

Key	Value
move_args_0.0	"5"
move_args_0.1	"5"
wait_args.0	"10"
urec_args_0.0	"region.0"
move_args_1.0	"0"
move_args_1.1	"0"

These values will have the agent move to location (5,5), wait 10 seconds, perform a Uniform Random Edge Coverage over region.0, wait 10 seconds, and then move to location (0,0).