Printer Friendly
The Free Library
22,710,190 articles and books

Plan sharing: showcasing coordinated UAV formation flight.



Agent teaming and autonomy are foundational themes in multi-agent systems. Agents may work as singletons or they may work in environments where other agents exist. In multi-agent systems, agents may form teams by sharing common goals with other agents. Cooperation is essential for any collaborative, group activity. Beyond coordination and judicious role assignment, cooperation enables members of a team to be aware and account for collection of their goals as well as the performance of agents on individual goals. This paper presents a general model of cooperation and illustrates how it may enhance group performance. In this paper, we present results of an application of the concept of cooperation in a simulated swarm of reconnaissance urban UAVs that are tracking vehicles in an urban environment.

Keywords: agents, collaboration, UAV, benevolence BENEVOLENCE, duty. The doing a kind action to another, from mere good will, without any legal obligation. It is a moral duty only, and it cannot be enforced by law. A good wan is benevolent to the poor, but no law can compel him to be so.

BENEVOLENCE, English law.
, help

Povzetek: Opisanje splosni model sodelovanja agentov.

1 Introduction

An agent is defined as an autonomous, problem-solving computational entity capable of effective operation in dynamic and open environments (Luck and Griffiths, 2003). A multi-agent system is a system of agents that exhibit social rationality, normative patterns, and values, among themselves within an environment (Hexmoor, 2003).

Typically, each agent in a multi-agent system possesses incomplete information for solving a problem with limited global knowledge. Therefore, agents interact with one another to gather information, act upon that information, and hence collectively solve a problem. Collaborative, behavior-coordinated activity involves participants to work jointly with each other to satisfy a shared goal that often yields more than the sum of individual actions (Grosz grosz  
n. pl. gro·szy
See Table at currency.



[Polish, from Czech gro
 and Sidner, 1990). The mentioned type of activity may be distinguished from both interaction and simple coordination in terms of the commitments agents make to each other (Grosz and Kraus, 1996).

A theory of collaboration must therefore account for not only intentions, abilities, and knowledge about actions of individual agents, but also for their coordination in group planning and group acting. Furthermore, it must account for the manner in which plans may be incrementally formed and executed by the participants.

Agents may have different beliefs concerning the methods for performing an action or those for achieving a desired state. Pollack argued for a view of plans as purely data-structures (Pollack, 1990) i.e., a plan is more appropriately viewed as a set of partially ordered actions that, when performed under appropriate conditions, lead to a specified new state of the world. She has argued for a view of plans as mental states that are necessary for plan interference. Having a plan does not merely require the know-how to perform a behavior, but it also includes possessing the intention to perform the actions entailed.

To adequately model cooperation, it is necessary to accommodate differences among beliefs of individual participants as well as to distinguish between knowledge about action performance and the intention to act. Agents may differ not only in their beliefs about the strategies to perform an action and the state of the world, but also in their assessments of the ability and willingness of an individual to perform an action.

The shared plan formalization for·mal·ize  
tr.v. for·mal·ized, for·mal·iz·ing, for·mal·iz·es
1. To give a definite form or shape to.

2.
a. To make formal.

b.
 provides mental state specifications of both shared plans and individual plans. Shared plans are constructed by groups of cooperative agents and include subsidiary shared plans formed by subgroups as well as subsidiary individual plans formed by individual participants in the group (Lochbaum, 1994). The formalization distinguishes between complete plans in which all the requisite beliefs and intentions have been established and partial plans. In addition to the propositional attitude propositional attitude

Psychological state expressed by a verb that may take a subordinate clause beginning with “that” as its complement. Verbs such as “believe,” “hope,” “fear,” “desire,”
 of intending to perform an action, it introduces the attitude of intending that a proposition be held.

Agents can enhance their fitness by mutual help rather than by competition, as is observed in nature (Benton, 2001). This assumes that resources adequate for both agents exist, or are created by interacting and sharing their information. This enhances both, the process of working together toward a common goal as well as the process of sharing effort, expertise and resources to achieve mutually desirable outcome.

Figure 1 illustrates that the coordination process and role assignment are subsets of the process of cooperation. The later, in turn, is a part of the collaboration process.

[FIGURE 1 OMITTED]

Agents need to organize themselves in a manner that permits them to perform their tasks efficiently. A malformed mal·formed
adj.
Abnormally or faultily formed.
 organization will affect the entire multi-agent system. When multi-agent systems change state, the agents in the system should be able to organize themselves accordingly by sharing information amongst them. When this is not accomplished, cooperation should be adapted in order to avoid disruption in the multi-agent system.

We have applied the just mentioned concept to a simulated swarm of reconnaissance Unmanned Arial Vehicles (UAVs) that are tracking vehicles in an urban environment with details discussed in Section 3.

This paper offers an approach to adapt cooperation in multi-agent systems. The main focus will be particularly on the cooperation among agents who are working together for a particular task while using the plan sharing techniques to enhance the cooperation. Rudimentary metrics are developed to gauge the effect of collaboration on system performance.

The novelties of this paper are in the following areas:

* Developing superior strategies for a given set of agents to work together

* Devising a process by which the agents are integrated into a team, regulated to achieve team goals

* Increasing agents' performance to contribute to a high functioning system.

* Evaluating agents during the process of cooperation.

* Quantifying the effect of cooperation on the goals and the system performance.

In the remainder of this paper, Section 2 contains related work in the area of cooperation between the agents and also the application of the cooperation in multi UAV interactions. In this section, issues related to cooperation, necessity of cooperation, and plan sharing among the agents are discussed. Application of cooperation and collaboration in our implemented UAV swarm is presented in section 3. Section 4 outlines a novel, generalized cooperation algorithm. We describe the importance of cooperation by illustrating how agent plan sharing enhances the cooperation process. Section 5 briefly describes incorporation of collaboration in our UAV swarm. We then present experiments and results in section 6. Section 7 provides concluding remarks and suggestions for future work.

2 Related Work

Since there is a growing demand for robust and intelligent multi-agent systems, a vast body of work is available in the area of group activity (Hexmoor, 2003).

According to according to
prep.
1. As stated or indicated by; on the authority of: according to historians.

2. In keeping with: according to instructions.

3.
 Alonso, two agents may depend on one another in one of sixteen ways (Alonso, et. al., 1999). Sharing a goal achievement is central to forming agent teams (Cohen cohen
 or kohen

(Hebrew: “priest”) Jewish priest descended from Zadok (a descendant of Aaron), priest at the First Temple of Jerusalem. The biblical priesthood was hereditary and male.
, et.al., 1997). Agents that want to maximize their gain may consider cooperation in order to lower their workload and temporal penalties (Beer et. al, 1999). Hexmoor extended the explorations for teaming (Hexmoor and Duchscherer, 2001).

An understanding of collaboration is essential to modeling the intentional context of discourse and its structure (Grosz and Sidner, 1990; Lochbaum, et.al., 1990 and Lochbaum, 1995, 1998). As a theoretical framework for modeling collaboration (Grosz and Kraus, 1996), it is evident that collaborative activities require a complex set of parameters that must be taken into account. The primary focus while attempting to achieve a goal is on understanding the states of mind of the individuals who participate in collaboration, and on properties of the group. An overview of the model designed by Grosz provides a setting in which to examine the roles of parameters of agents on collaborative plans and activities (Grosz, 1999).

In this process, the mutual beliefs of the discourse participants, the amount of knowledge that each individual participant or all participants should have, which was discussed in (Clark and Richard, 1981; Cohen, 1981) as well as differences in beliefs among participants in a discourse are important (Pollack, 1990).

Partial, individual plans are expanded to more complete plans through means-ends reasoning about intended goals. Cooperation mirrors this reasoning process, i.e., plan-collaboration process. However, their expansion requires communication and negotiation as well as means-ends reasoning about the way in which to perform the group action (Grosz and Kraus, 1999).

By and large, communication and collaboration are disjoint dis·joint
v.
To put out of joint; dislocate.
; yet interdependent activities. Communication is inherently a collaborative activity (Grosz and Sidner, 1990; Korta, 1995 and Arrazola, 1996). An agent communicates to achieve a purpose. The motivations underlying communication provide structure for an agent's discourse (Mataric, 1993). Collaboration, in turn, requires communication. Both communication and collaboration can be used parametrically in agent design. As a result, theories and models of collaboration are essential to understand and model intentional states and the intentional attributes of discourse (Grosz and Sidner, 1990; Lochbaum, Grosz and Sidner, 1990 and Lochbaum, 1995, 1998), which use the Shared Plans formalization of collaboration, as the basis of a computational model
For another meaning, see Model of computation
Computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation.
 for recognizing the intentional structure of disclosure.

Building directly on Lochbaum's use of Shared plans, others have constructed a collaborative graphical interface See GUI.  for a travel planning system See spreadsheet and financial planning system. . These applications use the logical specification provided by shared plans to constrain utterance generation and interpretation, e.g., (Rich and Sidner, 1994) and (Sidner and Rich, 1997).

Furthermore, in a collaborative activity, collaboration commonly occurs within the process of planning. Each agent may have incomplete or incorrect beliefs. Furthermore, their beliefs about each other's beliefs and capabilities to act may be incorrect. As a result, a collaborative act cannot be modeled simply by aggregating plans of individual agents.

Therefore, rather than modeling plan recognition, what must be modeled is the augmentation of beliefs about the actions of multiple agents and their intentions. Thus, Grosz and Sidner modified and expanded the Shared plan model of collaborative behavior originally proposed in (Grosz and Sidner, 1990), to present an algorithm for updating an agent's beliefs about a partial, shared plan, and describe an initial implementation of this algorithm in the domain of network management for augmenting an evolving jointly-held plan.

For a multi-agent collaborative control, Chandler and Pachter conclude that decision making through planning and management are the essence of the autonomous control problem (Chandler and Patcher, 1998).

To improve teamwork, we need to better understand the nature of coordination and its ramifications. This is explained with in-depth analysis of the coordination that is required to carry on a conversation.

For investigation of cooperative control of multiple UAVs, a simulator is offered (Chandler and Rasmussen, 2001). This is implemented in a hierarchal manner where inter-vehicle communication is explicitly modeled. During the construction of a UAV swarm, issues concerning memory usage and functional encapsulation (1) In object technology, the creation of self-contained modules that contain both the data and the processing. See object-oriented programming.

(2) The transmission of one network protocol within another.
 were also considered. This simulation has been instrumental in evaluating cooperative control strategies for UAVs.

Control Automation and Task Allocation (CATA), which is a multiple-vehicle/multi-agent simulation was developed at the Boeing Corporation. This simulation has been used in several early cooperative control studies, such as in (Chandler and Rasmussen, 2001). Since CATA was relatively large and written in C++, it proved to be difficult for widespread use.

A number of other UAV simulations exist. Their payload weight carrying capability, their accommodations (volume, environment), their mission profile (altitude, range, duration) and their command, control and data acquisition capabilities vary significantly; for a brief survey, See (Lua, et. al., 2003).

Recent military operations This is a list of missions, operations, and projects. Missions in support of other missions are not listed independently. World War I
''See also List of military engagements of World War I
  • Albion (1917)
 have showcased the abilities of UAVs where they provide intelligence, surveillance, reconnaissance, command, and control information to commanders in real-time or near real-time format. The success of UAVs has raised questions about future roles for UAVs in the military operation. These roles include arming UAVs and using UAVs for target designation; these missions are commonly grouped under the title of Unmanned Combat Aerial Vehicles (UCAVs), see (Raymond, 2000).

The ability to control many remote entities with minimal user intervention has many military and commercial applications. Current techniques for controlling UAVs, which rely on centralized control 1. In air defense, the control mode whereby a higher echelon makes direct target assignments to fire units. 2. In joint air operations, placing within one commander the responsibility and authority for planning, directing, and coordinating a military operation or group/category of  and on the availability of global information, are not suited to the control of UAV swarms owing to owing to
prep.
Because of; on account of: I couldn't attend, owing to illness.

owing to prepdebido a, por causa de 
 the complexity that arises from the interactions between swarm elements (Stover and Gibson, 1997).

Traditional, centralized approaches, frequently lead to exponential increases in communication bandwidth requirements Bandwidth requirements (communications)

The channel bandwidths needed to transmit various types of signals, using various processing schemes. Every signal observed in practice can be expressed as a sum (discrete or over a frequency continuum) of sinusoidal
 and in the size of the controlling swarm. In contrast, swarms of simple biological or artificial organisms exhibit rich, emergent behaviors, without the need for centralized control or global communication (Boanabeau, et.al., 1999). Controlling UAV swarms via human supervision is of great interest to the US military.

For coordination, as explained earlier, allocation of tasks to the UAV during their flight is one of the criteria for achieving the joint activity. Work for optimizing the task allocation problem for a fleet of Unmanned Aerial Vehicles with tightly coupled See tight coupling.  tasks and rigid relative timing constraints is available in (Alighanbari, et.al., 2003). The overall objective is to minimize the mission completion time for the fleet, and the task assignment must account for differing UAV capabilities and no-fly zones.

For many vehicles, obstacles, and targets, fleet coordination is a complicated optimization problem In computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. More formally, an optimization problem is a quadruple  and the computation time In computational complexity theory, computation time is a measure of how many steps are used by some abstract machine in a particular computation. For any given model of abstract machine, the computation time used by that abstract machine is a computational resource which can be  increases rapidly with the problem size (Pachter, et.al, 2002 and Richards, et.al., 2001).

Work on particle swarms (Parker, 1993), cultural algorithms (Reynolds and Chung, 1996), and bacterial chemo che·mo
n.
Chemotherapy or a chemotherapeutic treatment.
 taxis algorithms (Muller, et. al., 2002) has generalized the idea for abstract, n-dimensional cognitive spaces that make up self-organizing particle systems.

Interactions between particles result in complex global behavior which emerges from the joint actions and relatively simple behaviors of the individual particles, thereby exhibiting self-organization. These properties have been used in applications in computer graphics (Reynolds, 1987, 1999), multi-robot team control (Balch and Arkin, 1998; Fredslund and Matartic, 2002; Winder and Reggia, 2004; Vail and Veloso, 2003), and numerical optimization (Parker, 1993). We have implemented an Urban UAV test bed, described in the following section.

3 An Urban UAV surveillance system

UAVs in our simulation are modeled as powered aerial vehicles sustained in flight by aerodynamic lift Noun 1. aerodynamic lift - the component of the aerodynamic forces acting on an airfoil that opposes gravity
lift

aerodynamic force - forces acting on airfoils in motion relative to the air (or other gaseous fluids)
 and guided without an onboard crew. In general, a UAV may be expendable or recoverable, and can fly autonomously or be piloted remotely. When working together as a group, UAVs resemble a multi-agent system. UAVs interact with other UAVs and perform their tasks collectively.

Figure 2 depicts a typical flight pattern of a swarm of UAVs tracking terrestrial vehicles. The "white" circles depict cloud cover. Vehicles may temporarily disappear from UAV view when they are traveling below the randomly appearing clouds. This makes tracking them more challenging. UAVs need to interact to improve their collective tracking capability. Vehicles as well as cloud patches appear randomly in our simulation for a measure of realism. The system maintains the track quality, i.e., the number of cycles tracked, for each target, which is described in more detail as the Performance list and denoted as Perf [] in Section 4. Upon entry of a UAV in the theater, it determines a number of targets, i.e., vehicles, to track largely based on proximity. This is called a UAV Preference list denoted as Pref [], also described in Section 4.

[FIGURE 2 OMITTED]

Elsewhere, (Hexmoor, et. al., 2005) we have described how a human supervisor may guide and alter interactions among UAVs to improve system tracking. This is achieved primarily via parameters that affect a UAV social personality. These consist of four parameters.

* Dedication parameter determines how committed the UAVs are to reacquire lost targets.

* Sociability parameter determines how gregarious gre·gar·i·ous  
adj.
1. Seeking and enjoying the company of others; sociable. See Synonyms at social.

2. Tending to move in or form a group with others of the same kind: gregarious bird species.
 UAVs will be. A UAV with a positive sociability will tend to operate in proximity to other UAVs. Conversely, a UAV with negative sociability (i.e., anti-social) will make the UAV shun others and operate independently.

Conformity parameter determines how quickly the UAV reacts to operator suggestions. Finally, Disposition parameter determines how quickly a UAV will become frustrated with the negotiation process.

In contrast, herein we focus on a single parameter of Cooperation level, denoted as CL, further described in Section 4. This parameter is used to adjust the level of collaboration among UAVs. We have explored setting CL at four levels. The results of a set of experiments are presented in Section 6.

4 A Proposed Cooperation Model

Although we used the same collaboration model, in this section we describe our collaboration model in abstract terms those which express abstract ideas, as beauty, whiteness, roundness, without regarding any object in which they exist; or abstract terms are the names of orders, genera or species of things, in which there is a combination of similar qualities.

See also: Abstract
 and we will not refer to UAVs or target tracking. Our model chiefly concentrates on how agents team up to form a collaborative pattern to achieve their goals.

Upon entry, an agent determines its own intentions for a plan to achieve its goal. Each agent has its own individual plan for achieving its goals. The common goal refers to the collective set of agent goals to be achieved.

Each agent has knowledge of its environment in the form of beliefs. An agent will desire to perform its individual tasks by assessing its knowledge of the environment. After environmental assessment and determination of a course of action (i.e., a plan), it will form intentions to achieve its selected goals.

Next, we outline our model in general terms. Let there be n agents in a given environment. Assume in goals are to be achieved at any instant in time.

After updating beliefs, an agent compiles a list of goals to be achieved. By default, an agent will wish to follow the order of goals in its list. Each agent forms a course of action.

We consider all agents to be identical in every respect. Furthermore, agents are assumed to possess identical capabilities and limitations. To recapitulate re·ca·pit·u·late  
v. re·ca·pit·u·lat·ed, re·ca·pit·u·lat·ing, re·ca·pit·u·lates

v.tr.
1. To repeat in concise form.

2.
, in an environment with a team with in goals, each agent has its own courses of actions gleaned from its own personal observations.

Each agent may independently pursue its individual intentions. In some circumstances, agents might be successful in reaching their goals independently. However, this lack of interdependence might adversely affect the achievement of common goals.

Next, we outline a plan sharing process. Each agent shares its intentions, desires, and also the course of action in which it wants to proceed. In other words Adv. 1. in other words - otherwise stated; "in other words, we are broke"
put differently
, each agent has global knowledge about other agents' intentions and desires, and also about all the goals which have been already achieved. This includes updating the changed intentions of all agents. If an agent changes its desire and thus changes its intentions, this is shared with other agents in the environment.

Cooperation is uniformly introduced in the process of achieving goals. Agents are considered to have the same cooperation level. The system level performance is quantified as the overall cumulative performance of all the agents working in the system; that is, the number of goals processed in the duration of time. The rate of goal performance is broadcasted to other agents in the system, hence making it available for them to access.

During the cooperation process, each agent in each cycle considers its preferred intentions, the performance of each goal in the environment, and the predetermined cooperation level in the system. Tracking information (i.e., goal performance) is maintained locally on targets. This phenomenon provides a way for communication between UAV's where each UAV can access the tracking information on the targets. Cooperation level in our model is a system parameter for cooperativeness, shared by all agents. In each cycle, when agent decision making process considers the cooperation level in the environment, it generates a new bid order list which will be considered as the new intention list for each agent. enters

This new intention list is generated starting from the preference list of the particular agent and reflects changes to this preference list to favor the goals with low performance levels biased with the cooperation level.

For example, if a particular agent has a preference list of goals, say 3, 6, and 7. Assume the relative cumulative performance levels of these goals are 9, 21, and 11 respectively. Then without cooperation, agents may revise their goal list by comparing their preference list with the goal performance list. The revised list will be 6, 7 and 3. That means, here, the goal with less performance is given the least priority.

When cooperation is introduced in this example and with some global value for the cooperation level, the new, revised intention list will not only depend on the performance of the goals but also on the cooperation level among agents. We assume cooperation level to encapsulate en·cap·su·late
v.
1. To form a capsule or sheath around.

2. To become encapsulated.



en·cap
 an implicit notion of benevolence where agents tend to help one another achieve low performing goals. With cooperation, the revised example goal list will be 3, 7, 6. That means, here, the goal with less performance is given the highest priority.

Assume an agent has a goal g to be achieved and it has been trying it for a long period of time. Meanwhile, the agent concentrates only on the present goal, and by the time it plans to achieve the goal, which is the next one in its intention goal list, that goal might be unavailable for the agent due to unforeseen reasons. Here, benevolent agents might come forward to achieve this particular goal. Agents come forward even if goal g is less appealing due to its lack of performance.

Cooperative agents will act out their benevolence by striving to achieve poorly performing goals in order to exhibit cooperation. With the largest cooperation level values, agents will consider achieving the poorest performing goals. The summary of our model is thus as follows.

Consider an agent A in a given environment. It possesses its own beliefs, desires and intentions for achieving goals. Each agent constructs its own preference list of goals it wants to follow along with its individual plan. Let us denote the former as Pref[A]. Each goal in the list of goals of the environment is continually assessed and ascribed a performance level. This performance level is given depending on the number of times the goal has been attempted by agents in the environment. To summarize, each goal G has its instantaneous performance value codified cod·i·fy  
tr.v. cod·i·fied, cod·i·fy·ing, cod·i·fies
1. To reduce to a code: codify laws.

2. To arrange or systematize.
 with Perf [G].

In each cycle, each agent A considers its Pref [A], Perf [G], and Coop level. As shown in the Figure 3, a new bid order list for each agent is generated using performance and preference lists as input. If the cooperation level value is large the agent will prefer the poorest performing goals. The reordering of the agent preference list reflects the degree of the cooperation level.

[FIGURE 3 OMITTED]

Figure 4 presents a pseudocode for our cooperation algorithm, which demonstrates how an agent cooperates. An agent A's bid list, B[ ], is initialized to its preference list. CL is the cooperation level parameter set to a constant. The reorder re·or·der  
v. re·or·dered, re·or·der·ing, re·or·ders

v.tr.
1. To order (the same goods) again.

2. To straighten out or put in order again.

3. To rearrange.

v.
 list is set to the size of the preference list Pref [A]. During each iteration, reorder list is computed using the given equation. The new reorder list is sorted and is assigned as the agent's new bid list. Intuitively, lack of performance is amplified by the cooperation level constant CL. Capability of agent [A] is the capability to perform the goal i.

[FIGURE 4 OMITTED]

Suppose an agent's original preference list is [1, 2, 3] and the respective performance list of goals are [0.2, 0.7, 0.9]. Assume the cooperation level CL to be set at 0.75. Reorder list is computed:

For 1, reorder = 1 - 0.2 * 0.75 = 1 - 0.15 = 0.75 2, reorder = 1 - 0.7 * 0.75 = 1 - 0.525 = 0.475 3, reorder = 1 - 0.9 * 0.75 = 1 - 0.675 = 0.325

After sorting, we have [0.325, 0.475, 0.75], thus the new bid list is [3, 2, 1]. In this example we assume all agents are equally capable toward all goals, i.e., Capability[A, i] = 1.0.

5 Implementation and Experiments

Our cooperation algorithm (Figure 4) was applied to the UAV swarm system described in section 3. Here UAVs are agents and the goals are targets. An environment with different paradigms and parameters is used to achieve the simulation and experiments. The Java programming language is used to code the algorithms and the Borland JBuilder was used as our IDE.

Initializing all the UAVs with similar capabilities created the multi-agent system. All targets are initialized with similar qualities as well. Each UAV has its own preference list of targets and a performance list of all the targets in the corresponding preference list as mentioned in the algorithms. The initial positions of all UAVs are randomly generated. The preference list for each UAV is generated by the number of targets it has been able to sense in the environment. All the targets are mobile and keep moving.

The system is initially simulated without plan sharing and without cooperation. Then plan sharing process is introduced and the system is simulated at different levels of cooperation i.e., the cooperation level (CL) shown in the algorithm is assigned different values and then the system performance is captured by the simulation.

6 Results and Discussions

6.1 UAVs with no Plan-Sharing and no Cooperation

We used 200 UAVs for tracking, initially placed randomly, but then they move and values change. We first examined the system performance behavior when agents were not sharing plans nor cooperating with each other as shown in Figures 5 and 6. UAVs proceed with tasks in their preference list as they enter the system. As there is no cooperation or plan-sharing among the UAVs, the targets untracked during the given time cycle are not substantially decreased. As shown in the Figure 5, the targets untracked reach a steady state of about 194, given 225 as the total number of targets in the system.

[FIGURES 5-6 OMITTED]

Figure 6 shows the cumulative number of traces achieved, which is climaxed at about 332.

These results motivated us to introduce plan-Sharing and Cooperation as discussed in Section 5.

6.2 UAVs with Plan-Sharing but no cooperation

Next, we first introduced Plan-Sharing among UAVs where they share their preference list with every other UAV present in the system. Although there is no explicit cooperation, plan sharing helps UAVs account for a larger number of targets. An implicit style of cooperation takes place by targets that are tracked independently by multiple UAVs.

The decrease in the total number of untracked targets can be observed in Figure 7, at about 174, which is lower than that without plan-sharing. The enhancement in the system performance can also be observed as the total number of traces that increased up to 1248 in the Figure 8.

[FIGURES 7-8 OMITTED]

6.3 UAVs with Plan-Sharing and with the lowest level Cooperation

Next, we introduced plan sharing as well as the lowest level cooperation. UAVs work together and generate their own bid list as explained in the algorithm in section 5. Here the cooperation level threshold is set to the lowest level. The results are depicted in Figures 9 and 10.

[FIGURES 9-10 OMITTED]

As shown in Figure 9, the total number of untracked targets is reduced to about 139. The system performance is shown in Figure 10 where the total number of collective system traces has increased to 2896.

6.4 UAVs with Plan-Sharing and medium level cooperation

Here, the cooperation level is turned up to the medium level. With UAV bid list revised due to cooperation, performances are shown in Figures 11 and 12.

[FIGURES 11-12 OMITTED]

Total number of untracked targets has further decreased to 79 as shown in figure 11. System performance as the total number of traces has increased to 3445.

6.5 UAVs with Plan-Sharing and medium high level of cooperation

At the medium high cooperation level, UAV bid lists were more seriously revised and the results are shown in Figures 13 and 14.

[FIGURES 13-14 OMITTED]

The total number of untracked targets is further decreased to about 45 as shown in figure 13. Figure 14 shows an increase in the system performance to 4194.

6.6 UAVs with Plan-Sharing and with the highest level cooperation

Finally, we increased the cooperation level to the highest level and the results are shown in Figures 15 and 16.

[FIGURES 15-16 OMITTED]

The total number of untracked targets, shown in Figure 15, is reduced to 14. The system performance, shown in Figure 16 reached 5353 traces.

It is observed that system performance increases by increasing level of cooperation.

7 Conclusions and Future work

The primary focus of this paper was on an implicit sense of plan sharing where agents modify their plans in light of other agents' plans. Communication is a key form of interaction in multi-agent systems, where multiple agents collaborate to attain a common goal.

The concept of collaboration was elaborated in a strategy for cooperation. Certain cooperation techniques are better suited for our experiments. Plan sharing and collaborative plan refinements clearly demonstrated improved performance.

Further work will consider agents with different capabilities as well as plan and goal priorities. Along with deontological de·on·tol·o·gy  
n.
Ethical theory concerned with duties and rights.



[Greek deon, deont-, obligation, necessity (from ; see deu-1 in Indo-European roots) +
 notions of request and permission for collaboration, we will explore overlaps between collaboration, autonomy, and benevolence (Hexmoor, 2003).

Received: December 7, 2005

8 References

[1] Alighanbari M., Kuwata Y., and How J. P., "Coordination and Control of Multiple UAVs with Timing Constraints and Loitering," Space Systems Laboratory, IEEE (Institute of Electrical and Electronics Engineers, New York, www.ieee.org) A membership organization that includes engineers, scientists and students in electronics and allied fields.  proceedings 2003.

[2] Alonso G., Schuldt H., Schek H.J., "Transactional Coordination Agents for Composite Systems," Proceedings of the International Database Engineering and Applications Symposium (IDEAS'99). Montreal, Canada, August 1999.

[3] Arrazola X., "Collective Action: Logical Foundations for Interaction," report no. ILCLI-96-FCSAI-1. Donostia--San Sebastian: ILCLI, 1996.

[4] Balch T. and Arkin R., "Behavior-based Formation Control for Multi-robot teams," IEEE Robotics and Automation, 14(6), 926-939. 1998.

[5] Beer J. M., Whatley J., "Group Project Support Agents for helping students work online," HCI (Human Computer Interaction) Refers to the design and implementation of computer systems that people interact with. It includes desktop systems as well as embedded systems in all kinds of devices.  International 1999, Munich, Germany, Lawrence Erlbaum, London. 1999.

[6] Benton M.J., "Biodiversity on land and in the sea," Geological Journal, 36:211-230, 2001.

[7] Bonabeau E., Dorigo M. and Theraulaz G., "Swarm Intelligence Swarm intelligence (SI) is an artificial intelligence technique based around the study of collective behavior in decentralized, self-organized systems. The expression "swarm intelligence" was introduced by Gerardo Beni, Susan Hackwood, and Jing Wang in 1989, in the context of : From Natural to Artificial Systems," New York New York, state, United States
New York, Middle Atlantic state of the United States. It is bordered by Vermont, Massachusetts, Connecticut, and the Atlantic Ocean (E), New Jersey and Pennsylvania (S), Lakes Erie and Ontario and the Canadian province of
, NY: Oxford University, 1999.

[8] Chandler R., and Pachter M., "Research Issues in Autonomous Control of Tactical UAV's," proceedings of the American Control Conference, 1998, Vol.: 1, 24-26, pp.394-398. June 1998

[9] Chandler P., Schumaker C., Rasmussen S., "Task Allocation for Wide Area Search Munitions mu·ni·tion  
n.
War materiel, especially weapons and ammunition. Often used in the plural.

tr.v. mu·ni·tioned, mu·ni·tion·ing, mu·ni·tions
To supply with munitions.
 via Network Flow Optimization," AIAA GNC GNC General Nutrition Centers
GNC Gas Natural Comprimido (Argentina)
GNC Guidance, Navigation, and Control
GNC Grand National Championship (ATV racing)
GNC Global Navigation Chart
, Aug 2001.

[10] Clark R., "Uninhabited combat aerial vehicles: airpower air·pow·er or air power  
n.
1. The organized, integrated use of aircraft and missiles for purposes of foreign policy, strategy, operations, and tactics.

2. The tactical and strategic strength of a country's air force.
 by the people, for the people, but not with the people," Maxwell air force base Coordinates:

“Maxwell Field” redirects here. For other uses, see Maxwell Field (disambiguation).

Maxwell Air Force Base (IATA: MXF, ICAO: KMXF, FAA LID: MXF), officially known as
 al: air university press CADRE paper, 2000.

[11] Cohen, D.M., Moridae. In W. Fischer, G. Bianchi and W.B. Scott (eds), "FAO FAO,
n See Food and Agriculture Organization.
 species identification sheets for fishery purposes," Eastern Central Atlantic; fishing areas 34, 47 (in part). Vol. 3, FAO, Rome, 1981.

[12] Cohen, P. R., Levesque H. R., and Smith I., "On team formation," Hintikka, J. and Tuomela, R. (Eds.) Contemporary Action Theory. Synthese, 1997.

[13] Fredslund J. and Mataric M., "A General Algorithm for Robot Formations Using Local Sensing and Minimal Communication," IEEE Transactions on Robotics and Automation, 18(5):837-846. 2002.

[14] Grosz. B. and Sidner. C., "Plans of Discourse," In P. Cohen et.al, eds., Intentions in Communication. MIT MIT - Massachusetts Institute of Technology  press. Forthcoming, 1990.

[15] Grosz B., Sidner C. and Loachbaum K. E., "Models of plans of support communication: An initial report," In proceedings of AAAI-90, Boston, MA, 1990.

[16] Grosz B. and Kraus S., "Collaborative Plans for Complex Group Action," In Artificial Intelligence. 86(2), pp. 269-357. 1996.

[17] Grosz B., and Kraus, S., "The Evolution of SharedPlans," In Foundations and Theories of Rational Agencies, A. Rao and M. Wooldridge, eds. pp. 227-262, 1999.

[18] Hexmoor, H., Duchscherer H., "Efficiency as a Motivation to Team,". FLAIRS Conference 2001: 49-52, 2001.

[19] Hexmoor, H., "Weekly Dependent Agents may rely on their luck or Collaboration: A Case for Adaptation," In Proceedings of The Society for the Study of Artificial Intelligence and the Simulation of Behavior (AISB AISB As I Said Before
AISB American International School of Bucharest
AISB Association of Imaging Service Bureaus
AISB As It Should Be
AISB American International School of Budapest
AISB Ancient Illuminated Seers of Bavaria
), York, UK, 2003.

[20] Henry Hexmoor, Agent Autonomy in a group, A special issue of Journal of Connection Science, Taylor and Francis, 2003.

[21] Hexmoor, H., McLaughlin, B., and Baker, M., Swarm Control in Unmanned Aerial Vehicles, In Proceedings of International Conference on Artificial Intelligence (IC-AI), CSREA Press, 2005.

[22] Korta, K. and Larrazabal J. M. (eds.) "Semantics and Pragmatics pragmatics

In linguistics and philosophy, the study of the use of natural language in communication; more generally, the study of the relations between languages and their users.
 of Natural Language: Logical and Computational Aspects," Proceedings of the Donostia-Toulouse 1993 Workshop. Donostia: ILCLI Series No. 1. (ISBN ISBN
abbr.
International Standard Book Number


ISBN International Standard Book Number

ISBN n abbr (= International Standard Book Number) → ISBN m 
: 84-920104-3-6), 1995.

[23] Lochbanm K., "Using Collaborative Plans to Model the Intentional Structure of Discourse," PhD thesis, Harvard University Harvard University, mainly at Cambridge, Mass., including Harvard College, the oldest American college. Harvard College


Harvard College, originally for men, was founded in 1636 with a grant from the General Court of the Massachusetts Bay Colony.
, 1994.

[24] Lochbaum K., "The Use of Knowledge Precondition in Language Processing
For the processing of language by computers, see Natural language processing.


Language processing refers to the way human beings process speech or writing and understand it as language.
," In IJCAI IJCAI International Joint Conference on Artificial Intelligence
IJCAI International Joint Committee on Artificial Intelligence
9S, Proceedings of the 14th International Joint Conference on Artificial Intelligence The International Joint Conference on Artificial Intelligence (or IJCAI) a meeting of researchers from the different areas of artificial intelligence (AI). It is organized by the IJCAI, Inc. , pages 1260-1266, 1995.

[25] Lochbaum K., "A collaborative planning model of intentional structure," Computational Linguistics computational linguistics (CL)

Use of digital computers in linguistics research. The simplest examples are the use of computers to scan text and produce such aids as word lists, frequency counts, and concordances.
 24(4). 1998.

[26] Luck, M. and Griffiths, N., Coalition Formation Through Motivation and Trust. In Proceedings of the Second International Conference on Autonomous Agents and Multi-agent Systems (AAMAS 2003), ACM (Association for Computing Machinery, New York, www.acm.org) A membership organization founded in 1947 dedicated to advancing the arts and sciences of information processing. In addition to awards and publications, ACM also maintains special interest groups (SIGs) in the computer field.  Press, 2003.

[27] Lua, C.A., Altenburg, K., and Nygard, K.E., Synchronized Multi-Point Attack by Autonomous Reactive Vehicles with Simple Local Communication, Proceedings of IEEE Swarm Intelligence Symposium, 2003., 2003.

[28] Mataric, M.J., Kin recognition Kin recognition refers to animals' capabilities to distinguish between close genetic kin and non-kin. In evolutionary biology and in psychology, such capabilities are presumed to have evolved to serve the adaptive functions of kin altruism , similarity, and group behavior. In Fifteenth Annual Cognitive Science cognitive science

Interdisciplinary study that attempts to explain the cognitive processes of humans and some higher animals in terms of the manipulation of symbols using computational rules.
 Society Conference, pages 705-710. Lawrence Erlbaum Associates, June 1993.

[29] Muller, S., Marchetto J., Airaghi, S. and Kourmoutsakos, P., "Optimization Based on Bacterial Chemo taxis," IEEE Transactions on Evolutionary Computation The IEEE Transactions on Evolutionary Computation (TEC) is a monthly journal published by the Computational Intelligence Society of the IEEE Computer Society. It contains peer-reviewed articles and other contribitions in the area of Evolutionary Computation and Natural Computation. , 6:16-29. 2002.

[30] Parker, L., "Designing Control Laws for Cooperative Agent Teams," Proc. IEEE International Conference on Robotics and Automation, 3:582-587. 1993.

[31] Patcher, M., Chandler, P., Swaroop, D., Fowler, J., "Complexity in UAV cooperative control." ACC See adaptive cruise control.  2002. pp. 1831-1836. 2002.

[32] Pollack. M. E., "Plans as complex mental attitudes," in P. Cohen et. al., eds., Intentions in Communication. MIT press. Forthcoming, 1990.

[33] Raymond, R., Hill S., Dougherty, and Moore, J.T., "Model Signal Latency Effects Using Arena," Proceedings of the 2000 Winter Simulation Conference. 2000.

[34] Reynolds, C., Flocks, Herds and Schools, "Computer Graphics," 1987, 21:25-34. 1987.

[35] Reynolds, R., and Chung, C., "A Test bed for Solving Optimization Problems Using Cultural Algorithms," Evolutionary Programming evolutionary programming - (EP) A stochastic optimisation strategy originally conceived by Lawrence J. Fogel in 1960.

An initially random population of individuals (trial solutions) is created. Mutations are then applied to each individual to create new individuals.
, 225-236. 1996.

[36] Reynolds, C., "Steering Behaviors for Autonomous Characters," Proc. Game Developers Conf.1999, 763-782. 1999.

[37] Richards, A., Bellingham, J., Tillerson, M., and How, J., "Multi-Task Allocation and Path Planning for Cooperative UAVs," Second Annual Conference on Cooperative Control and Optimization, Nov 2001.

[38] Rich, C., Sidner, C. L., , "Adding a collaborative agent to graphical user interfaces," Symposium on User Interface Software and Technology, Proceedings of the 9th annual ACM symposium on User interface software and technology, 1994.

[39] Sidner, C. L., Rich C., "COLLAGEN. When Agents Collaborate with People," Proceedings of the First International Conference on Autonomous Agents (Agents'97), 1997.

[40] Stover, J.A., and Gibson, R.E., "Controller for Autonomous Device," US patent # 5, 642,467, Issued June 1997.

[41] Tuomela, R., "Cooperation", Kluwer Academic, 2000.

[42] Reggia, J. and Winder, R., "Distributed Partial Memories to Improve Self-Organizing Collective Movements," IEEE Transactions. SMC SMC Saint Mary's College
SMC Santa Monica College
SMC Solaris Management Console
SMC Smooth Muscle Cell
SMC Small Magellanic Cloud (also see LMC)
SMC Safety Management Certificate (maritime shipping) 
 B, 2004, 34: 1967-1707. 2004.

[43] Vail D. and Veloso, "Multi-Robot Dynamic Role Assignment and Coordination through Shared Potential Fields," In Multi-Robot Systems. A. Shultz, L. Parker, and F. Schneider (editors), Kluwer, 2003.

Henry Hexmoor, Swetha Eluru and Hadi Sabaa

Department of Computer Engineering and Computer Science

University of Arkansas The University of Arkansas strives to be known as a "nationally competitive, student-centered research university serving Arkansas and the world." The school recently completed its "Campaign for the 21st Century," in which the university raised more than $1 billion for the school, used  

Fayetteville, AR 72701, USA.

E-mail: {Hexmoor, seluru, hsabaa}@uark.edu
COPYRIGHT 2006 Slovenian Society Informatika
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2006 Gale, Cengage Learning. All rights reserved.

 Reader Opinion

Title:

Comment:



 

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:unmanned aerial vehicle
Author:Hexmoor, Henry; Eluru, Swetha; Sabaa, Hadi
Publication:Informatica
Geographic Code:1USA
Date:Jun 1, 2006
Words:5802
Previous Article:Captain Nemo: a metasearch engine with personalized hierarchical search space.
Next Article:An Integration rule processing algorithm and execution environment for distributed component integration.
Topics:

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters