Distributed artificial intelligence: Difference between revisions

Revision as of 05:29, 16 October 2011

Latest revision as of 12:41, 13 April 2025

(85 intermediate revisions by 51 users not shown)

Line 1:

{{Short description|Subfield of artificial intelligence}}

{{no footnotes|date=February 2011}}

{{more refs|date=February 2023}}

'''Distributed artificial intelligence (DAI)''' is a subfield of [[artificial intelligence]] research dedicated to the development of distributed solutions for complex problems regarded as requiring intelligence. DAI is closely related to and a predecessor of the field of [[Multi-agent system|Multi-Agent Systems]].

{{Artificial intelligence}}

{{Multi-agent system}}

'''Distributed artificial intelligence''' ('''DAI''') also called Decentralized Artificial Intelligence<ref name=Demazeau>Demazeau, Yves, and J-P. Müller, eds. Decentralized Ai. Vol. 2. Elsevier, 1990.</ref> is a subfield of [[artificial intelligence]] research dedicated to the development of distributed solutions for problems. DAI is closely related to and a predecessor of the field of [[multi-agent system]]s.

== Objective ==

There are many reasons for wanting to distribute intelligence or cope with multi-agent systems. Mainstreams in DAI research include the following:

Multi-agent systems and distributed problem solving are the two main DAI approaches. There are numerous applications and tools.

==Definition==

Distributed Artificial Intelligence (DAI) is an approach to solving complex learning, [[automated planning|planning]], and decision-making problems. It is [[embarrassingly parallel]], thus able to exploit large scale computation and [[spatial distribution]] of [[System resource|computing resources]]. These properties allow it to solve problems that require the processing of very large [[data set]]s. DAI systems consist of autonomous learning [[Processing mode|processing nodes]] ([[Intelligent agent|agents]]), that are distributed, often at a very large scale. DAI nodes can act independently, and partial solutions are integrated by communication between nodes, [[Asynchrony (computer programming)|often asynchronously]]. By virtue of their scale, DAI systems are robust and elastic, and by necessity, loosely coupled. Furthermore, DAI systems are built to be adaptive to changes in the problem definition or underlying data sets due to the scale and difficulty in redeployment.

DAI systems do not require all the relevant data to be [[Aggregate data|aggregated]] in a single ___location, in contrast to [[Monolithic application|monolithic]] or [[Centralized computing|centralized]] Artificial Intelligence systems which have tightly coupled and geographically close processing nodes. Therefore, DAI systems often operate on sub-samples or hashed impressions of very large [[Training, validation, and test data sets|datasets]]. In addition, the source dataset may change or be updated during the course of the execution of a DAI system.

==Development==

In 1975 distributed artificial intelligence emerged as a subfield of artificial intelligence that dealt with interactions of intelligent agents.<ref name=Chaib>{{cite journal |last1=Chaib-Draa |first1=Brahim |last2=Moulin |first2=B. |last3=Mandiau |first3=R. |last4=Millot |first4=P. |title=Trends in distributed artificial intelligence |journal=Artificial Intelligence Review |date=1992 |volume=6 |issue=1 |pages=35–66 |doi=10.1007/BF00155579|s2cid=15730245 }}</ref> Distributed artificial intelligence systems were conceived as a group of intelligent entities, called agents, that interacted by cooperation, by coexistence or by competition. DAI is categorized into multi-agent systems and distributed problem solving.<ref name="Bond Gasser">{{cite book |editor1-last=Bond |editor1-first=Alan H. |editor2-last=Gasser |editor2-first=Les |title=Readings in distributed artificial intelligence |date=1988 |publisher=Morgan Kaufmann Publishers |___location=San Mateo, California |isbn=9781483214443 |url=https://www.sciencedirect.com/book/9780934613637/readings-in-distributed-artificial-intelligence}}</ref> In [[multi-agent system]]s the main focus is how agents coordinate their knowledge and activities. For distributed problem solving the major focus is how the problem is decomposed and the solutions are synthesized.

==Goals==

The objectives of Distributed Artificial Intelligence are to solve the [[automated reasoning|reasoning]], planning, learning and perception problems of [[artificial intelligence]], especially if they require large data, by distributing the problem to autonomous processing nodes (agents). To reach the objective, DAI requires:

* A [[Distributed computing|distributed system]] with robust and elastic computation on unreliable and failing resources that are loosely coupled

* Coordination of the actions and communication of the nodes

* Subsamples of large data sets and [[online machine learning]]

There are many reasons for wanting to distribute intelligence or cope with multi-agent systems. Mainstream problems in DAI research include the following:

* Parallel problem solving: mainly deals with how classic artificial intelligence concepts can be modified, so that [[multiprocessor]] systems and clusters of computers can be used to speed up calculation.

* Distributed [[problem solving]] (DPS): the concept of [[Intelligent agent|agent]], autonomous entities that can communicate with each other, was developed to serve as an [[abstraction]] for developing DPS systems. See below for further details.

* Multi-Agent Based Simulation (MABS): a branch of DAI that builds the foundation for simulations that need to analyze not only phenomena at [[macroscopic|macro]] level but also at [[microscopic scale|micro]] level, as it is in many [[social simulation]] scenarios.

==Approaches==

Two types of DAI has emerged:

* In [[Multi-agent system]]s agents coordinate their knowledge and activities and reason about the processes of coordination. Agents are physical or virtual entities that can act, perceive its environment and communicate with other agents. The agent is autonomous and has skills to achieve goals. The agents change the state of their environment by their actions. There are a number of different coordination techniques.<ref name="Jennings">{{cite book |last1=Jennings |first1=Nick |editor1=Gregory M. P. O'Hare |editor2=N. R. Jennings |title=Foundations of Distributed Artificial Intelligence |date=1996 |publisher=Wiley |___location=New York |chapter=Coordination Techniques for Distributed Artificial Intelligence |pages=187−210 |chapter-url=https://philpapers.org/rec/JENFOD |isbn=978-0-471-00675-6 |archive-date=1 November 2018 |archive-url=https://web.archive.org/web/20181101052328/https://eprints.soton.ac.uk/252187/1/FOUND%2DDAI%2DCOORD.pdf }}</ref>

* In distributed problem solving the work is divided among nodes and the knowledge is shared. The main concerns are task decomposition and synthesis of the knowledge and solutions.

DAI can apply a bottom-up approach to AI, similar to the [[subsumption architecture]] as well as the traditional top-down

==Agents and Multi-agent systems==

approach of AI. In addition, DAI can also be a vehicle for [[emergence]].

Notion of Agents: Agents can be described as distinct entities with standard boundaries and interfaces designed for problem solving.

Notion of Multi-Agents:Multi-Agent system is defined as a network of agents which are loosely coupled working as a single entity like society for problem solving that an individual agent cannot solve.

===Challenges===

The challenges in Distributed AI are:

# How to carry out communication and interaction of agents and which communication language or protocols should be used.

# How to ensure the coherency of agents.

# How to synthesise the results among 'intelligent agents' group by formulation, description, decomposition and allocation.

==Applications and tools==

Areas where DAI have been applied are:

* [[E-commerce|Electronic commerce]], e.g. for [[Trading strategy|trading strategies]] the DAI system learns financial trading rules from subsamples of very large samples of financial data

* [[Telecommunications network|Networks]], e.g. in [[telecommunications]] the DAI system controls the cooperative resources in a [[Wireless LAN|WLAN]] network<ref>{{cite web|author1=Anita Raja |author2=Linda Xie|author2-link= Jiang Xie |author3=Ivan Howitt |author4=Shanjun Cheng |others= Project sponsor: NSF |title=WLAN Resource Management using Distributed Constraint Optimization |id=CS Research: Past projects – Project summary |url=http://dair.uncc.edu/projects/past-projects/wlan-resource |archive-url=https://web.archive.org/web/20150512081820/http://dair.uncc.edu/projects/past-projects/wlan-resource |archive-date=2015-05-12 |website=UNC Charlotte: Department of Computer Science}} [https://cci.charlotte.edu/departments/computer-science-cs/cs-research UNC Charlotte College of Computing and Informatics]</ref>

* [[Scheduling (production processes)|Routing]], e.g. model vehicle flow in transport networks

* [[Scheduling (production processes)|Scheduling]], e.g. [[flow shop scheduling]] where the [[resource management]] entity ensures local optimization and cooperation for global and local consistency

* [[Search engine|Search engines]], e.g. in LLM [[Federated search|federated search]] like Ithy where document retrieval and analysis are distributed to DAI agents before aggregation <ref>{{cite web|title=Ithy: A distributed AI search engine|url=https://ithy.com}}</ref>

* Multi-Agent systems, e.g. [[artificial life]], the study of [[Artificial life|simulated life]]

* Electric power systems, e.g. Condition Monitoring Multi-Agent System (COMMAS) applied to transformer condition monitoring, and IntelliTEAM II Automatic Restoration System<ref>{{Cite journal|last1=Catterson|first1=Victoria M.|last2=Davidson|first2=Euan M.|last3=McArthur|first3=Stephen D. J.|date=2012-03-01|title=Practical applications of multi-agent systems in electric power systems|journal=European Transactions on Electrical Power|language=en|volume=22|issue=2|pages=235–252|doi=10.1002/etep.619|issn=1546-3109|url=https://strathprints.strath.ac.uk/33136/1/Catterson9830393_File000000_173961975.pdf}}</ref>

DAI integration in tools has included:

* ECStar is a distributed rule-based learning system.<ref>{{cite web |title=Anyscale Learning For All {{!}} alfagroup |url=http://groups.csail.mit.edu/EVO-DesignOpt/groupWebSite/index.php?n=Site.BP#ECStar-fig |website=alfagroup.csail.mit.edu}}</ref>

==Agents==

===Systems: Agents and multi-agents===

{{Further|Multi-agent system#Applications}}

Notion of Agents: Agents can be described as distinct entities with standard boundaries and interfaces designed for problem solving.

Notion of Multi-Agents: Multi-Agent system is defined as a network of agents which are loosely coupled working as a single entity like society for problem solving that an individual agent cannot solve.

===Software agents===

The key concept used in DPS and MABS is the abstraction called [[software agent]]s. An agent is a virtual (or physical) [[Wiktionary:autonomy|autonomous]] entity that has an understanding of its environment and acts upon it. An agent is usually able to communicate with other agents in the same system to achieve a common goal, that one agent alone could not achieve. This communication system uses an [[agent communication language]].

== Software agents ==

The key concept used in DPS and MABS is the abstraction called [[software agent]]s. An agent is a virtual (or physical) [[Wiktionary:autonomy|autonomous]] entity that has an understanding of its environment and acts upon it. An agent is usually able to communicate with other agents in the same system to achieve a common goal, that one agent alone could not achieve. This communicate system uses an [[agent communication language]].

A first classification that is useful is to divide agents into:

Line 28 ⟶ 70:

Well-recognized agent architectures that describe how an agent is internally structured are:

* [[SoarASMO (cognitive architecture)|SoarASMO]] (aemergence rule-basedof approachdistributed modules)

* [[BDI software agent|BDI]] (Believe Desire Intention, a general architecture that describes how plans are made)

* [[InterRAP]] (A three-layer architecture, with a reactive, a deliberative and a social layer)

* PECS (Physics, Emotion, Cognition, Social, describes how those four parts influences the agents behavior).

* [[Soar (cognitive architecture)|Soar]] (a rule-based approach)

== BasicSee Disadvantagesalso ==

The Basic Problems of Distributed AI are:

1.How to carry out communication and interaction of agents and which communication language or protocols should be used.

* {{Annotated link |Collective intelligence}}

2.How to ensure the coherency of agents.

* {{Annotated link |Federated learning}}

* {{Annotated link |Simulated reality}}

3.How to synthesise the results among 'intelligent agents' group by formulation,description,decomposition and allocation.

* {{Annotated link |Swarm Intelligence}}

==Real time Applications==

<ref>{{cite book|last=Ferber|first=Jacques|title=Multi-Agent System: An Introduction to Distributed Artificial Intelligence}}</ref>

#Problem Solving

#Multi-Agent Simulation

#Construction of Synthetic Worlds

#Collective Robotics

#Kenetic Program Design

== Application in Industries ==

=== Demand for multi-agent systems ===

Industries have large number of different environments which are always interacting with each other.There are a number of intelligent agents which communicate with each other. Each agent has its own sphere of influence which is influenced or controlled by that agent.Spheres may be overlapping of some of the agents so there is a need to define dependency relationships between the agents.For achieving agile manufacturing conventional [[Computer integrated manufacturing]] techniques need to be modified.<ref>{{cite book|last=Wooldridge|first=Michael|title=MultiAgent Systems}}</ref>

==== Demand of agility ====

Agile is a process of development in which continuous changes appear and process is successful in accommodating those changes. Manufacturers with shorter product cycle are able to keep track of needs in customer needs thus increasing market share.Agility requires system to be low in cost, having quick response, ability to correct itself in presence of faults. Agility has an impact on most part of product manufacture cycle and production system is one of them.

Characteristics of agility

{| class="wikitable"

|-

! !! Cost !! Response Time !! Quality !! Scope !! Relation to Agility

|-

| '''Agile''' ||Low || Quick || Self-healing || Limitless ||

|-

| '''Flexible''' || Low || Fast || Strong || Limited || Superseded

|-

| '''Lean''' || High || Slow || Fragile || Little || Complemented

|}

==== Problems with conventional CIM systems ====

Computer integrated manufacturing is a highly centralized system. It has a central computer which has all database and provides overall view of state of system for both internal representation and also interface to rest of environment.It also maintains schedule and is responsible for all activities dispatch, their scheduling and management.Problems with this approach are

*It depends on single system.

*Relies on global plans.

*Each action to be performed requires planning and scheduling.

These increase the problems of [[Scheduling (production processes)|Manufacturing scheduling and control]] like

*Stochasticity- impact of external noise such as machine breakdown.<ref>{{cite book|last=5th international conference, CPAIOR 2008, Paris, France, May 20-23, 2008 : proceedings|title=Integration of AI and OR techniques in constraint programming for combinatorial optimization problems}}</ref>

*Tractability- impact of large number of interacting operations.

*Decidability- operational implications made from factory's turing machine equivalent.

*Formalchaos- sensitivity to initial conditions.

A centralised system is more susceptible to tractability because, the number of entities in industries interacting and to be managed is large and may lead to combinatorial explosion.Also it is difficult to implement agile systems in presence of such difficulties. Centralised systems are complex and costly.

==== Manufacturing scheduling and control(MSC) approaches ====

''Heuristic Dispatching''

In Heuristic Dispatching a simple rule is used to decide the next step to be taken in process. It may be like select the process with shortest remaining process time. Many such rules are evaluated for their performance on parameters like total cost per job, number of late jobs, machine and labor utilization. Dispatching rules must be simple to implement. Only one heuristic may not be sufficient for one process to decide new step and a combination of many heuristics may be required.

''Numerical Programming''

Linear and integer programming are often used to provide formulations of scheduling problems.New algorithms combined with powerful hardware make it possible to solve substantial problems using these techniques.They provide an approximate optimal solution. But they may get trapped in problem of combinatorial explosion.Also they are complex so large investment is required in sophisticated processors or have to agree to slower outputs.

''Traditional AI''

It tries to implement satisficing approach to scheduling by accounting semantic information about ___domain, applying heuristic judiciously and selectively. Numerical solutions are not always possible due to cost and optimal solution solution is not always required.Symbolic computation has evolved which is faster than numeric but they are not suitable where configuration and load changes daily.

''Advanced Heuristic''

It involves combination of all techniques depending on the system whose scheduling is to be done.Heuristic, simulation techniques and optimization principles are combined to give optimal solution. It is better than a single simple heuristic.

=== How can Multi agent system help? ===

==== Characteristics ====

Multi agent allows production system to be decentralised, each agent can takeits own action and allows concurrent execution rather than sequential.Autonomous agents have a local view of system replacing central computer with complete view of system and they have the ability to respond to an event locally. These agents perform depending on interactions in real time and their activities are not influenced by a global plan.Schedules emerge from independent decisions of local agents. There is no need of alternate cycles of scheduling and execution.Each agent is close to its own environment. Each action of agent is in sync with local environment and thus system adjusts automatically to the local noises and changes in agents.

==== When multi agent systems should be used?====

Multi agent system is desirable in systems which require following characteristics in their systems

''Distribution''-Multi agent systems are distributed in nature as they are self dependent and take decisions based on their local environment. It is desirable to have distributed approach if a company has number of branches which need to work independently.

''Factorisation''-Power of industry production system comes from division of work among agents each responsible for that particular tool, entity and all information about it. This simplifies information gathering and operations.

''Variability''- It is easy to manage a system with conventional sequential scheduling if values of its variables do not change over time. But if values of variable vary large over time then multi agent must be used.

=== Taxonomy of multi agent system ===

There are several taxonomies introduced by multiagent system. Dimensions of Distributed artificial intelligence<ref>{{cite book|last=Keith S. Decker|title=Distributed problem solving: A survey}}</ref> are

*Agent granularity (coarse vs. fine)

*Heterogeneity of agent knowledge (redundant vs. specialized)

*Methods of distributing control (benevolent vs. competitive, team vs. hierarchical, static vs. shifting roles)

*and Communication possibilities (blackboard vs. messages, low-level vs. high-level, content)

In dimension 1 and 4 multiagent system have coarse granularity and high communication while in others they vary across whole range.

Taxonomy is also defined from application perspective.<ref>{{cite book|last=N. R. Jennings|title=Foundations of Distributed Artificial Intelligence|year=1996|publisher=Wiley Interscience}}</ref>

*System function

*Agent architecture(degree of heterogeneity, reactive vs. deliberative)

*System architecture(communication, protocols, human involvement)

Important contribution of this perspective is that it helps us differentiate between agent and system dimensions.

Various multiagent scenarios and issues arising in them are<ref>{{cite web|title=http://www.cs.cmu.edu/afs/cs/usr/pstone/public/papers/97MAS-survey/node3.html#complexity}}</ref>

'''Homogeneous Non communicating agents'''

*reactive vs deliberative agents

*local or global perspective

*modeling of other agent state

*how to affect others

'''Heterogeneous Non communicating agent'''

*Benevolence vs competitiveness

*Evolving agents

*Modeling of others goal,action or knowledge

*Resource management

'''Heterogeneous communicating agent'''

*Understanding each other

*Planning communicative acts

*Benevolence vs competitiveness

*Resource management

*Commitment/decommitment

Three group of perspectives are important for multiagent system applied in industries.

==== Application function ====

In industries multiagent systems are used mainly for functions like production and design. Function of production includes scheduling to a large extent and to small extent monitoring and diagnosis.Such system endow distributed entities with some level of local intelligence.Systems which support design function have multiple agents which help designers coordinate their designs and thus reducing conflicts which helps in manufacturing.Some system also deal with manufacturing functions like power distribution, information integration and logistics.

==== Individual agent architecture ====

Here it seen how similar they are to each other to interact and how sophisticated is their reasoning.

''<big>How diverse are agents from each other?</big>''

Agents in a multiagent system must interact with each other. For interaction there must be something in common with each other, they may be having different functions but they share common architecture which helps them in communication.Only digital messages is not only way to communicate but also through their effects on environment.in this case the common thing between agents is the sensor shared by both agents.

''<big>How sophisticated is individual agents reasoning</big>?''

Tasks performed by agents vary from simple giving response to sensors to taking decisions similar to humans.So there is a need for agents to have a varying level of sophistication to suit the tasks assigned to them. ''Self consciousness'' level of sophistication requires that agents must know of the existence of other agents.''Social'' level of sophistication can identify other agents state, goal and plans to modify its own action for better interaction.Artificial agents act as an interface to humans by providing them information and then getting commands from them thus they are augmenting human operator.

''<big>Combining reaction and planning</big>'' <ref>{{cite web|title=http://www.agent.ai/doc/upload/200302/paru96_2.pdf}}</ref>

When we add more capabilities to individual agents by sophisticating their their reasoning capabilities we need to utilise it in a way as to benefit the system. This efficient utilisation can be achieved by combining reaction and planning .

[[File:Planning and reaction.jpg|thumb|Add caption here]]

''Pure reaction''-In this type there is no way to control the reaction. As there is no planning it is fast but inflexible.It is suitable in applications where all possibilities of tasks are known and there are no changes in it.

[[File:Reaction and planning.jpg|thumb|Add caption here]]

''Reaction overridden by plan''-In this planner is assigned to monitor the sensors and the reactions being taken by reactors on input from sensors.When reactor disagrees with the decision of planner ,planner pushes its own decision on the effectors.It is slow as decisions are planned by planner.This model is applicable in cases where there is uncertainty.Reactor takes care of anticipated requirements while planner takes care of uncertain situations.

[[File:Planning reaction.jpg|thumb|Add caption here]]

''Reaction modified by plan''-In this planner can rewire the reactor in real time such that if a similar output comes from sensor, planner gives it to effector so that actions are performed at reaction speed.Rewiring is done by software.It is used in real time applications such as applying emergency corrections to real time systems.

== See also ==

* [[Collective intelligence]]

== References ==

{{Reflist}}

<!--- After listing your sources please cite them using inline citations and place them after the information they cite. Please see http://en.wikipedia.org/wiki/Wikipedia:REFB for instructions on how to add citations. --->

== Further reading ==

* Hewitt, Carl; and Jeff Inman (November/December 1991). "DAI Betwixt and Between: From 'Intelligent Agents' to Open Systems Science" ''IEEE Transactions on Systems, Man, and Cybernetics''. Volume: 21 Issue: 6, pps. 1409–1419. ISSN 0018-9472

* Grace, David; Zhang, Honggang (August 2012). ''Cognitive Communications: Distributed Artificial Intelligence(DAI), Regulatory Policy and Economics, Implementation''. John Wiley & Sons Press. {{ISBN|978-1-119-95150-6}}

* {{cite book | last1=Shoham | first1=Yoav | last2=Leyton-Brown | first2=Kevin | title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations | publisher=[[Cambridge University Press]] | isbn=978-0-521-89943-7 | url=http://www.masfoundations.org/download.html | year=2009 | ___location=New York}}

* Sun, Ron, (2005). ''Cognition and Multi-Agent Interaction''. New York: Cambridge University Press. {{ISBN |978-05218396480-521-83964-8}}

* {{cite journal |last1=Trentesaux |first1=Damien |last2= Philippe |first2=Pesin |last3=Tahon |first3=Christian |title= Distributed artificial intelligence for FMS scheduling, control and design support |journal=Journal of Intelligent Manufacturing |date=2000 |volume=11 |issue=6 |pages=573–589 |doi=10.1023/A:1026556507109|s2cid=36570655 }}

* {{cite book | last=Vlassis | first2=Nikos | title=A Concise Introduction to Multiagent Systems and Distributed Artificial Intelligence

* {{cite book |last1=Vlassis |first1=Nikos |title=A Concise Introduction to Multiagent Systems and Distributed Artificial Intelligence

| publisher=Morgan & Claypool Publishers | isbn=978-1-598-29526-9 | year=2008 | ___location=San Rafael, CA}}

|publisher=Morgan & Claypool Publishers |isbn=978-1-59829-526-9 |date=2007 |___location=San Rafael, CA}}

{{Authority control}}

{{DEFAULTSORT:Distributed Artificial Intelligence}}

[[Category:Multi-agent systems]]

[[Category:Artificial intelligence]]

{{DEFAULTSORT:Distributed Artificial Intelligence}}

[[fr:Intelligence artificielle distribuée]]

[[Category:Distributed artificial intelligence| ]]