Multi-agent system

Posted: Tháng Bảy 1, 2013 in AgentProgramming

A multi-agent system (M.A.S.) is a computerized system composed of multiple interacting intelligent agents within an environment. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve. Intelligence may include some methodic, functional, procedural or algorithmic search, find and processing approach.

Topics where multi-agent systems research may deliver an appropriate approach include online trading,[1] disaster response,[2] and modelling social structures.[3]

Multi-agent systems consist of agents and their environment. Typically multi-agent systems research refers to software agents. However, the agents in a multi-agent system could equally well be robots,[4] humans or human teams. A multi-agent system may contain combined human-agent teams.

Agents can be divided into different types:

  • Very simple like: passive agents[5] or agent without goals (like obstacle, apple or key in any simple simulation)
  • Active agents[5] with simple goals (like birds in flocking, or wolf–sheep in prey-predator model)
  • Or very complex agents (like cognitive agent, which has a lot of complex calculations)

Environment also can be divided into:

  • Virtual Environment
  • Discrete Environment
  • Continuous Environment

Agent environments can be organized according to various properties like: accessibility (depending on if it is possible to gather complete information about the environment), determinism (if an action performed in the environment causes a definite effect), dynamics (how many entities influence the environment in the moment), discreteness (whether the number of possible actions in the environment is finite), episodicity (whether agent actions in certain time periods influence other periods),[6] and dimensionality (whether spatial characteristics are important factors of the environment and the agent considers space in its decision making).[7] Agent actions in the environment are typically mediated via an appropriate middleware. This middleware offers a first-class design abstraction for multi-agent systems, providing means to govern resource access and agent coordination.[8]

IntelligentAgent-SimpleReflexIntelligentAgent-Learning

Characteristics

The agents in a multi-agent system have several important characteristics:[9]

  • Autonomy: the agents are at least partially independent, self-aware, autonomous
  • Local views: no agent has a full global view of the system, or the system is too complex for an agent to make practical use of such knowledge
  • Decentralization: there is no designated controlling agent (or the system is effectively reduced to a monolithic system)[10]

Self-organization and self-steering

Multi-agent systems can manifest self-organization as well as self-steering and other control paradigms and related complex behaviors even when the individual strategies of all their agents are simple.

When agents can share knowledge using any agreed language, within the constraints of the system’s communication protocol, the approach may lead to a common improvement. Example languages are Knowledge Query Manipulation Language (KQML) or FIPA’s Agent Communication Language (ACL).

Systems paradigms

Many M.A. systems are implemented in computer simulations, stepping the system through discrete “time steps”. The MAS components communicate typically using a weighted request matrix, e.g.

 Speed-VERY_IMPORTANT: min=45 mph, 
 Path length-MEDIUM_IMPORTANCE: max=60 expectedMax=40, 
 Max-Weight-UNIMPORTANT 
 Contract Priority-REGULAR

and a weighted response matrix, e.g.

 Speed-min:50 but only if weather sunny,  
 Path length:25 for sunny / 46 for rainy
 Contract Priority-REGULAR
 note - ambulance will override this priority and you'll have to wait

A challenge-response-contract scheme is common in MAS systems, where

 First a "Who can?" question is distributed.
 Only the relevant components respond: "I can, at this price".
 Finally, a contract is set up, usually in several more short communication steps between sides,

also considering other components, evolving “contracts”, and the restriction sets of the component algorithms.

Another paradigm commonly used with MAS systems is the pheromone, where components “leave” information for other components “next in line” or “in the vicinity”. These “pheromones” may “evaporate” with time, that is their values may decrease (or increase) with time.

Properties

M.A. systems, also referred to as “self-organized systems”, tend to find the best solution for their problems “without intervention”. There is high similarity here to physical phenomena, such as energy minimizing, where physical objects tend to reach the lowest energy possible within the physically constrained world. For example: many of the cars entering a metropolis in the morning will be available for leaving that same metropolis in the evening.

The main feature which is achieved when developing multi-agent systems, if they work, is flexibility, since a multi-agent system can be added to, modified and reconstructed, without the need for detailed rewriting of the application. These systems also tend to be rapidly self-recovering and failure proof, usually due to the heavy redundancy of components and the self managed features, referred to above.

The study of multi-agent systems

The study of multi-agent systems is “concerned with the development and analysis of sophisticated AI problem-solving and control architectures for both single-agent and multiple-agent systems.”[11] Topics of research in MAS include:

  • agent-oriented software engineering
  • beliefs, desires, and intentions (BDI)
  • cooperation and coordination
  • organization
  • communication
  • negotiation
  • distributed problem solving
  • multi-agent learning
  • scientific communities (e.g., on biological flocking, language evolution, and economics) [12][13]
  • dependability and fault-tolerance
  • robotics,[14] Multi-robot systems (MRS), Robotic clusters

Frameworks

While ad hoc multi-agent systems are often created from scratch by researchers and developers, some frameworks have arisen that implement common standards (such as the FIPA agent system platforms and communication languages). These frameworks save developers time and also aid in the standardization of MAS development. One such developmental framework for robotics is given in [15]

See Comparison of agent-based modeling software.

Applications in the real world

Multi-agent systems are applied in the real world to graphical applications such as computer games. Agent systems have been used in films.[16] They are also used for coordinated defence systems. Other applications include transportation, logistics,[17] graphics, GIS as well as in many other fields. It is widely being advocated for use in networking and mobile technologies, to achieve automatic and dynamic load balancing, high scalability, and self-healing networks.

Source: http://en.wikipedia.org/wiki/Multi-agent_systems

Agent-oriented programming (AOP) is a programming paradigm where the construction of the software is centered around the concept of software agents. In contrast to object-oriented programming which has objects (providing methods with variable parameters) at its core, AOP has externally specified agents (with interfaces and messaging capabilities) at its core. They can be thought of as abstractions of objects. Exchanged messages are interpreted by receiving “agents”, in a way specific to its class of agents.

OOP AOP
Basic unit object agent
Parameters defining state of basic unit unconstrained beliefs, commitments, capabilities, choices….
Process of computation message passing and response methods message passing and response methods
Types of message unconstrained inform, request, offer, promise, decline….
Constraints on methods none honesty, consistency….

Advertisements

Nhà văn Yann Martel đã đạt giải thưởng Booker với cuốn tiểu thuyết “Cuộc đời của Pi” (Life of Pi).  Tác phẩm này đã được đạo diễn nổi tiếng của phim “Ngọa Hổ Tàng Long” Lý An chuyển thành bộ phim nhựa thu hút hàng triệu khán giả trên thế giới trong thời gian vừa qua. Đó là một câu chuyện về cuộc hành trình kỳ diệu của Pi, nhân vật chính của phim với Richard Parker, một con hổ Bengal của công ty bố mình và quá trình khám phá bản thân mình, đức tin và thượng đế.

Tuyệt phẩm thu hút người xem với nhiều khung ảnh trực quan quyến rũ. Bạn có quyền phê bình và đánh giá nội dung, nhưng nhiều người xem sẽ thừa nhận rằng có một số bài học lớn trong cuộc sống và kinh doanh mà có thể học từ phim “Cuộc đời của Pi”:

1.    Nếu bạn tin vào mọi thứ thì rốt cuộc bạn sẽ không tin vào điều gì cả.

Cha của Pi Santosh Patel nói điều này với Pi tại bàn ăn trong một buổi ăn tối khi ông nhận ra sự tò mò của con trai về các tôn giáo khác nhau và muốn làm theo các tôn giáo ấy cùng một lúc.  Lời nói của ông đã đúng không chỉ trong tín ngưỡng tôn giáo mà trong cả cuộc sống hàng ngày cũng như trong kinh doanh. Thật khó để đi theo nhiều con đường khác nhau cùng một lúc. Nếu ai đó làm như vậy thì họ tự mâu thuẫn với chính mình, tạo ra sự nhầm lẫn, mất sự tập trung và nhất là lãng phí các nguồn tài nguyên quan trọng. Là một doanh nhân, bạn phải chọn cho mình người hướng dẫn, cố vấn giỏi và thực hiện những lời khuyên một cách khôn ngoan. Nếu lắng nghe tất cả các lời khuyên, lời tư vấn  bạn sẽ hạn chế chính bạn trong việc nắm bắt cơ hội và chậm trễ trong việc thực hiện mục tiêu cuối cùng của bạn. Là doanh nhân bạn phải chọn cho mình một mô hình kinh doanh  một cách cẩn thận và nên thực hiện nó như một đức tin để đi đến mục tiêu. Trong những ngày đầu, điều quan trọng là người doanh nhân phải chọn cho mình sự ưu tiên và những phân khúc cụ thể để tiến hành chiến lược. Theo đuổi nhiều con đường khác nhau cùng một lúc sẽ nhanh chóng hủy hoại nguồn lực  và cuối cùng là vỡ mộng với toàn bộ quá trình.

2.    Xây dựng thương hiệu rất quan trọng.

Pi Patel  sinh ra với tên Piscina Molitor Patel được đặt bởi ông chú của mình phía sau  một bễ bơi ở Pháp. Cách phát âm của tên này đã tạo cho Pi rất nhiều đau khổ, vì nó trở thành những câu chuyện hài hước trong trường học cũng như ngoài đời. Anh đã sớm nhận ra sự phiền toái của tên mình và cố gắng giải thích nó là bắt đầu bằng chữ Pi trong chữ cái Hy Lạp cho từng người, từng nhóm người… tuy  nhiên tình hình không có vẻ khá hơn.  Anh đã quyết định tự nhớ giá trị Pi (π) với hàng trăm số lẻ của nó và chứng minh trên lớp cho mọi người biết đến khả năng của mình. Và từ đó người ta gọi cậu là Pi. Pi đã thành công khi gắn một câu chuyện với cái tên của mình. Trong kinh doanh cũng vậy, khi tạo ra một thương hiệu mới hay muốn thay đổi một thương hiệu hiện tại đang có vấn đề của mình, bạn cần tạo ra một câu chuyện để nắm bắt trí tưởng tượng và trí nhớ của khán giả hay khách hàng tiềm năng về thương hiệu đó.  Trước khi đặt một thương hiệu mới phải thật cẩn trọng, vì làm lại thượng hiệu vừa đắt tiền vừa tốn rất nhiều thời gian như Pi Tatel đã thực hiện.  Chọn một thương hiệu tốt có thể là bước đầu tiên hướng tới xây dựng một thương hiệu thành công.

3.    Lập kế hoạch là điều cần thiết chứ không phải là tùy chọn.

Khi chiếc tàu bị chìm, Pi được ném xuống biển trên một chiếc tàu cứu sinh  với một số lượng thực phẩm và đồ cấp cứu rất hạn chế. Pi buộc phải thực hiện một kế hoạch sống sót với một thời gian không chắc chắn trên vùng biểu sâu và khắc nghiệt. May mắn thay anh đã tìm ra một cuốn sổ tay giúp anh lập được kế hoạch cho thời gian sống sót của mình. Nếu bạn là doanh nhân, hãy suy nghĩ về cuốn sổ tay và kế hoạch kinh doanh của mình. Điều quan trọng là bản kế hoạch luôn ở bên cạnh bạn, luôn nghiêm túc thực hiện theo kế hoạch, một khi bạn có sự hoài nghi nào đó, hãy xem xét và thực hiện theo kế hoạch. Khi khởi nghiệp, điều quan trọng nhất với mỗi doanh nhân là tiền. Bạn phải hoạch định nguồn tài nguyên tài chính đủ cho đến khi có nguồn thu nhập bán hàng hay khoản đầu tư mới, để luôn giữa vững dòng tiền kinh doanh, cũng giống như giữ nguồn năng lượng cho cuộc hành trình. Trong cuộc sống cũng vậy, bạn phải lập kế hoạch cho nhiều tình huống khác nhau, ngay cả khi nguồn thu nhập thấp, bạn vẫn có thể có một cuộc sống ý nghĩa.

4.    Đừng để tất cả các trứng vào một giỏ

Khi Pi bất ngờ tìm thấy con hổ Richard Parker trên thuyền cứu sinh, anh quyết định ném tất cả vật dụng và thức ăn dự trữ trền thuyền sang chiếc bè, cột chiếc bè với thuyền cứu sinh và quyết định chuyển sang sống trên chiếc bè để tránh bị con hổ ăn thịt. Ngay lúc đó, nó trông có vẻ là một quyết định khôn ngoan vì anh vẫn chưa hình dung được những nguy hiểm lớn hơn mà anh chưa bao giờ biết đến. Vào một buổi tối, một con cá voi khổng lồ xuất hiện lật úp chiến bè, vất đi tất cả nguồn thực phẩm dự trữ và nước ngọt. Lúc đó Pi nhận ra rằng sống chung với con hổ Parker trên thuyền có thể là một sự lựa chọn tốt hơn. Khi bắt đầu khởi nghiệp, nguồn tài nguyên thường khan hiếm  và điều quan trọng  là ngăn chặn sự rò rỉ và mất mát. Thật tốt để có một nguồn tài nguyên ổn định để tiếp cận thị trường. Bước vào một lãnh thổ không rõ, khai phá một thị trường không nghiên cứu và ném toàn bộ nguồn lực của mình vào thị trường, không xây dựng cho bạn một sân sau để rút lui là một sai lầm chết người. Nếu bạn có nhiều sản phẩm nhưng chỉ có một nguồn tài nguyên thì cách tốt nhất là chia nguồn lực theo từng nhóm sản phẩm tránh sự phụ thuộc vào chỉ một sản phẩm thành công, vì giai đoạn khởi nghiệp thường không chắc chắn. Trong cuộc sống, nếu bạn muốn đầu tư cho một tương lai tốt hơn, bạn đừng nên dồn hết toàn bộ nguồn tài nguyên có sẳn cho một sự lựa chọn. Trong sự nghiệp, hãy luôn nâng cao kỹ năng của mình theo yêu cầu thực tế của thị trường việc làm, không nên trói mình hoàn toàn vào công việc hiện tại trong một thời gian dài.

5.    Tìm hiểu để cùng tồn tại

Sau sự cố cá voi, Pi nảy ra ý định cần phải “hòa giải” với hổ Parker để cùng sống trên tàu cứu sinh, một ý tưởng mà anh luôn gạt bỏ từ trước tới nay. Bước đầu tiên, anh bắt đầu giao tiếp với Parker bằng cách huấn luyện, đánh dấu lãnh thổ và thiết lập một số quy tắc.  Sống cùng Parker trên thyền, anh luôn giữ chính mình ở trạng thái cảnh giác. Nhưng khi Parker đói bụng và nhảy xuống biển bắt cá, Pi đã giúp nó trở lại thuyền một cách từ từ. Parker được xem là một nhà đồng sáng lập và cũng là đối thủ cạnh tranh trong suốt hành trình (kinh doanh) của Pi. Một doanh nhân, bạn phải tồn tại và sống với cả hai đối tượng như vậy. Với đối tác đồng sáng lập, điều quan trọng để giao tiếp rõ ràng là xác định vai trò, trách nhiệm và đảm bảo rằng bạn không vi phạm không gian của nhau. Là một doanh nhân bạn phải tìm cách cùng sống với đối thủ cạnh tranh của mình, và luôn cảnh giác để đảm bảo bạn không bị đánh bại. Để cạnh tranh lành mạnh bạn không nên dễ dàng chọn những cách thức thực hiện phi đạo đức, hay các chiến thuật bẩn thỉu để chiếm lấy thị phần. Thậm chí đôi khi vừa cạnh tranh vừa giúp đối thủ của mình nếu nó giúp thị trường tổng thể phát triển.

6.    Luôn tiếp tục di chuyển

Khi Pi bị trôi dạt đến một hòn đảo bí ẩn của tảo ăn thịt người, nó có vẻ như anh bị trôi dạt đến một ốc đào dồi dào thực phẩm và nước ngọt, là một nơi trú ẩn lý tưởng. Nếu hài lòng thì nó cũng tương tự như việc tìm ra một giải pháp trung bình cho một vấn đề chiến lược. Tuy nhiên, càng về cuối của cuộc hành trình thì thường là phần khó khăn nhất, vì lúc đó cơ thể và tâm trí luôn có ý muốn từ bỏ. Hay cũng có thể có những thỏa hiệp dễ dàng và đầy nguy hiểm cũng giống như nếu Pi quyết định sống trên đảo với đầy loài tảo ăn thịt vào ban đêm. Trong kinh doanh cũng vậy, hãy giữ cho mình luôn di chuyển và không được tự mãn với những thành công tạm thời. Điều quan trọng là luôn để mắt và tâm trí đến mục tiêu cuối cùng. Pi đã quan sát cách tồn tại của những sinh vật trên đảo để tìm ra cách thức tồn tại của chính mình. Là doanh nhân, cần phải luôn nắm bắt thị trường, luôn tìm cách tung ra những sản phẩm mới, tốt hơn để chiếm lấy những khoảng trống của thị phần. Đôi khi bạn cũng phải quyết định thay đổi mô hình kinh doanh nếu thị trường đòi hỏi bạn phải thực hiện như vậy.

7.    Đừng bỏ cuộc

Cuộc đời của Pi là một câu chuyện của tính kiên trì, không bao giờ bỏ cuộc thậm chí trong những điều kiện khắc nghiệt nhất. Cho dù giữa đại dương bao la, bão to, sóng lớn, cá voi, hỗ dữ… Pi không bao giờ từ bỏ hy vọng sống sót.

Tương tự như vậy, một doanh nhân cần có những đức tính này, những ngày đen tối rồi sẽ trôi qua. Điều quan trọng là đừng bao giờ từ bỏ ước mơ của bạn – từ bỏ cuộc sống.  Sẽ có những lúc bạn rơi vào trạng thái tuyệt vọng, gần như bên bờ vực phá sản, nhưng cũng giống như triết lý vô thường của cuộc sống những khó khăn cũng là tạm thời. Ngay cả khi bạn đã thử hết tất cả mọi cách thì bạn cũng có khả năng thử lại chỉ có điều là làm nhiều hơn một chút. Hãy luôn nhớ rằng, luôn có ai đó quan sát bạn và bạn luôn có lý do để cố gắng. Sẽ luôn có cơ hội cho bạn như Pi khi đang đói bỗng nhiên có cá bay cung cấp thực phẩm, có cơn mưa rào cung cấp nước ngọt, có hòn đảo để nghỉ ngơi… và tiếp tục ủng hộ bạn đi đến thành công miễn là bạn không từ bỏ.

Phim Cuộc sống của Pi có thể có nhiều bài học tiết lý sâu sắc khác, nhưng với kinh doanh, khởi nghiệp, các doanh nhân trẻ sẽ học rất nhiều từ bộ phim này.

 Vân Anh (Tổng hợp)