Надійне генерування плану багатьма агентами і їх виконання за допомогою планувальників теоретичних рішень

3.2    Multiagent Protocols

When heterogeneous agents are active and each agent has a limited set of capabilities, goals at the individual and global level often require the interaction of multiple agents. It is also conceivable that tasks exist that require the parallel interaction of a group of agents. These types of interactions require the formation of teams of agents that are capable of developing joint plans. In addition, agents within a team must be aware of the social structure of their joint plans and act to preserve that structure if possible. One simple and cheap approach to supporting interaction among agents is to build teams off-line. In a changing environment, however, teams that are flexible and dynamic are more adaptable and appropriate. Dynamic collaborations allow agents to enter and leave teams as necessary to solve problems and allow an agent to evaluate whom it wishes to work with based on its current context. The proposed process for collaborative planning consists of three phases: coalition formation, coalition plan development, and commitment management.

  Coalition formation is the process of forming collaborations between agents to achieve a task. This process would be started by an agent if the agent was unable to perform a required task on its own. This may be caused by an agent having insufficient resources or not having the appropriate capabilities. These situations arise because agent plans are not limited to just ordering over actions in each agent, but instead are attempts to enter high utility states. To handle this type of situation, a contract action will also be executable by each agent. This contract action allows an agent, if it cannot bring about a high utility state locally, to find another agent which can perform the appropriate set of tasks. As an example of this process, consider a chemical agent on an exploration mission (This example is similar to ones used in testing CASPER [11]). The chemical agent is responsible for performing an experiment on a sample and then sending the results to a scientist agent. The scientist agent integrates data from multiple agents and determines various properties about the sample. Assume the chemical agent's high utility states are ovenPrepped, sampleAnalyzed, and sampleProcessed. These states are all initially false. The chemical agent can perform a PREP action to bring about ovenPrepped, and an OVEN action to make sampleAnalyzed true. The next step is to bring about sampleProcessed. Since the chemical agent does not have an action to bring about this state, it attempts to find an agent that does, leading it to search for a scientist agent that agrees to perform analysis.

  The formation protocol is similar to other agent-based team formation protocols [32] [50] and consists of discovery, proposal, and reply. Discovery consists of the requesting agent (the agent that is unable to perform a task) searching for another agent that is capable of achieve the task. Discovery could be implemented through broadcast messages, directory services, or direct knowledge of the abilities and resources of other agents. Once an appropriate task agent has been found, the requesting agent sends a proposal for the task to be performed with a list of constraints on performance that satisfy its requirements. For example, a science agent may request a chemical analysis agent to perform a certain measurement and return the results by a specific time. Upon receiving a request, the task agent evaluates the proposal in terms of utility and schedulability. If execution of the task is schedulable and beneficial, the task agent accepts the proposal and plan development is entered. Alternatively, the task agent may reject the task proposal or counter-propose. If a reject response is received, the original requesting agent is triggered to search for other task agents and potentially re-examine its own plan.

  A finalized joint plan leads to the developments of commitments between a group of interacting agents. Respecting commitments is key to the success of distributed planning. When a joint plan has been developed, each agent stores information about the commitments that have been made. This information includes the actions to be performed, constraints on those actions, and to whom the agent is committed to perform such actions. Agents use this commitment information to support task notification, determining who needs to be notified when a collaborative task is completed or the plan for a collaborative task is updated. Plan updates include updates for when a task has been rescheduled, when a task is taking longer then expected, or when an agent believes a task will fail. Commitments also guide future local planning. If an alternative plan under consideration requires breaking a commitment, the utility of adopting such a plan should include a negative utility representing the cost of the broken commitment. Preservation of the sanctity of commitments supports environments where social and globally directed activities are of high importance and helps to prevent a wave of broken commitments if there are high levels of task and agent interdependence. It also deters agents from being myopic and constantly switching plans in attempts to reach local optima.

  It is possible that certain actions will require the concurrent interaction of multiple agents during execution. An example of this type of action would be multi-robot beam lifting in a construction domain [52]. In such cases, the collaboration formation protocol could be extended to send multiple requests at the same time to a set of appropriate agents.

  The process of selecting an agent to request collaboration with could be implemented in multiple ways and is a potential area of future research interest. Ideally, agents would select the agent they feel is most appropriate to perform a given action. Appropriateness could be determined from previous interactions, models of trustworthiness, and knowledge of the current plans and load of the other agents. An alternative and inexpensive method would be to randomly select an agent from the set of agents that is capable of performing the task. This would reduce computational costs in the requesting agent in determining suitable collaborators, but is more likely to lead to rejections and longer periods of negotiation.

  To evaluate a task request, an agent is interested in determining whether achieving a task would be useful given its state of the world, its social philosophy, its current plan, and its schedule. The dynamic decision network of the agent is the mechanism used for this evaluation. The decision network determines the utility of actions based on both the agents domain model and its philosophical principles that have been mapped to utilities. To incorporate an external task request into a DDN, a request variable can be set as true in the agent's domain model. For example, a domain model for an agent that can deliver coffee and mail may have deliverCoffeeRequest and deliverMailRequest nodes. When a request to deliver mail is received from an external agent, the agent can set this belief as true. In effect, this adds a new subgoal for the agent. The agent can then select high utility actions to perform through its planning process. If these high utility actions satisfy the new subgoal, the agent should accept the proposed task and update its current plan with the new ordering of high utility actions it has generated. However, if the newly generated actions are the same as the agent's original plan or do not make significant progress on the requested task, the agent should reject the proposal as performance of the the new task is not beneficial at the current time. If the appropriate actions for accomplishing a task do not appear in the agent's plan, the agent can not fulfill the request in the foreseeable future. This does not mean, however, that the agent could not fulfill the request at sometime later, but beyond its planning horizon, the agent is too unsure of the world to try to predict its state or the utility of actions and commit to any activities. Alternatively, the agent may generate actions that achieve the appropriate state, but not under the same constraints as originally proposed. If this occurs, the agent should reject the initial

proposal with a counter-proposal that contains the task and the new constraints under which the agent believes it can achieve the task. If one of the constraints on the proposed task is a deadline constraint, the agent should also perform its prediction of the time to accomplish the task. Given this prediction, the agent could counter-propose a new deadline for the task. Upon receiving a counter-proposal, the contractor agent can predict its expected utility through the DDN given the proposed constraints from the counter-proposal. If this state is acceptable to the contractor agent, allowing it to accomplish its own goals, it accepts the counter proposal or rejects. If it rejects the counter-proposal, it should then attempt to re-plan or find another agent to fulfill the task.

  At an abstract level, this approach is very similar to that taken by GPGP and many other approaches to task allocation. Each approach begins with a contractor agent that needs another agent to produce results or perform a task. This contractor determines which other agents are appropriate to perform such a task and proposes the task and constraints on its execution to a contractee agent. This contractee then locally determines whether it should accept the task. Several steps of negotiation may be used to adjust the proposed constraints. Upon acceptance of the task, a committment is made between the contractee and the contracter to perform the work, allowing the contractor to continue planning with belief that the task will actually be executed. There are significant differences, however, between the proposed approach and GPGP in how these steps are implemented, particularly in the contractee evaluation of whether to accept a task.

  When agents are considering whether to perform an action in the current implementation of GPGP, their choice is dependent on the marginal gain and cost of the action [57]. If the utility gain to the contractor is greater than the cost that will be absorbed by the contractee in performing the action, the contractee agent will accept the action. If the cost for the contractee is greater than the contractor gain with the original proposal, the contractee searches for constraints that allow execution of the action with reduced costs. This type of negotiation is defined [57] as multi-step one try and continues until an acceptable proposal is found. In single step negotiation, the agent would not search for a method that allows performance of the task, but solely reject the initial proposal. Multi-step multiple(n) negotiation allows for further negotiation after a satisfying proposal is accepted. Agents can continue negotiation to determine if a greater marginal utility can be found (usually by finding a method of accomplishing the task that reduces the cost for the contractee even further). The agents in this process make their decisions based on local utility -considering how potential actions affect only the agents involved in the negotiation.

  Agents in the proposed architecture view the question of task acceptance in a different light. Agents are designed expecting that they may be requested to perform certain actions and represent such a request as a variable in their DDN view of the world. To determine if an action should be accepted, the marginal gain and costs of the two negotiating agents is not considered. Instead, the contractee agent determines if it believes it is useful to perform a requested action. This is achieved by generating a temporary new plan with the knowledge of a requested task. If the plan steps generated by the DDN satisfy or move towards completion of the requested task, the agent will attempt to perform the task (either through acceptance or a counter-proposal). This approach relies on the fact that the DDN will return the actions that move the agent towards the highest utility states. If none of the generated actions move towards satisfaction of the requested task, then the task should not be accepted at the current time by the contractee agent. For some reason, its other goals are currently more important. The potential that contractee agents may always reject task proposals (a bad situation as proposals stem from agents that need a task performed but can't do it alone) should be limited as the DDN considers tasks in light of the agent's social philosophy during plan generation. Actions that are particularly useful in the context of a mission or global goals will lead the agent towards high utility states because of its philosophical preferences. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Додаток Б(ст.29-31)

Щоб здійснити синхронізацію, запропоновано, щоб  кожен агент підтримував  чергу плануваннязавданьякі виконають. Кожне із завданьвиконуватиметься з черги в тому порядку, який вимагає агент, але виконання здійснюється окремо, щоб запобігти потенційним неузгодженостям.

3.2 Протоколи мультиагента

Коли  гетерогенні агенти активні, і у кожного є обмежений набір здібностей, цілі на окремому і глобальному рівні часто вимагають взаємодії багатьох агентів. Також можливо, що існють завдання, які вимагають паралельної взаємодії групи агентів. Ці типи взаємодій вимагають формування команд агентів, які здатні розробити об'єднані плани. Крім того, агенти в межах команди мають бути обізнаними про соціальну структуру своїх об'єднаних планів і акту, щоб зберегти ту структуру, якщо можливо. Один простий і дешевий підхід підтримки взаємодії серед агентів має створити команди офлайн. Однак, у змінному середовищі гнучкі і динамічні команди є більш пристосованими і відповідними. Динамічна співпраця дозволяє агентам вводити і залишати команди залежно від необхідності, щоб вирішити проблеми і дозволити агенту оцінювати, з ким він хоче працювати, враховуючи його поточний контекст. Запропонований процес для сумісного планування складається з трьох фаз: формування коаліції, розвиток плану коаліції і управління зобов'язанням.

  Формування  коаліції - процес співпраці, що формується між агентами, щоб досягти завдання. Агнет ініціював би цей процес, якби він був не здатний самостійно виконати необхідне завдання. Це може зумовити агент, що має недостатні ресурси або не має відповідних здібностей. Такі ситуації виникають, тому що плани агента не обмежуються лише впорядковуванням залежно від дій у кожному агенті, але замість цього є спроби ввійти у стани високої корисності. Щоб керувати цим видом ситуації, дію контракту також виконуватиме кожен агент. Ця дія контракту дозволяє агенту, якщо він не може, викликати стан високої корисності в місцевому масштабі, щоб знайти іншого агента, який може виконати відповідний набір завдань. Як приклад цього процесу, розгляньте хімічного агента під час  місії дослідження (Цей приклад подібний до того, який використовували в тестуванні КАСПЕРА [11]). Хімічний агент відповідальний за здійснення експерименту на зразку і потім – за відправлення результатів науковому агенту. Науковий агент об'єднує дані від багатьох агентів і визначає різні властивості про зразок. Припустимо що стани високої корисності хімічного агента - ovenPrepped, sampleAnalyzed, і sampleProcessed. Ці всі стани спочатку неправильні. Хімічний агент може виконати дію PREP, щоб викликати ovenPrepped, і дія OVEN, щоб зробити sampleAnalyzed правильним. Наступний крок має викликати sampleProcessed. Оскільки хімічний агент не має дії, щоб викликати цей стан, він намагається знайти агента, який це робить, що призводить до пошуку агента ученого, який погоджується виконати аналіз.

  Протокол  формування подібний до інших протоколів, що базуються на формуванні командами  агентів[32] [50] і складається з  відкриття, пропозиці і відповіді. Відкриття складається з агента вимоги (агент, який не здатний виконати завдання), пошуку іншого агента, який здатний виконати завдання. Відкриття можна здійснити через широкомовні повідомлення, служби каталогу або шляхом відомостей про вміння й ресурси інших агентів. Як тільки відповідний агент завдання знайдено, агент вимоги відправляє пропозицію.для виконання завдання зі списком обмежень на виконання, які задовольняють її вимоги. Наприклад, науковий агент може просити хімічного аналітичного агента виконати певні вимірювання і повернути результати до певного часу. Отримавши запит агент завдання оцінює пропозицію з точки зору корисності і можливості запланованості.Якщо виконання завдання можна запланувати і воно є вигідним, агент завдання визнає, що запроваджується розвиток пропозиції і плану. Альтернативно, агент завдання може відхиляти пропозицію завдання або протидіяти їй. Якщо відповідь відмови одержано,  оригінальний агент вимоги починає шукати інших агентів завдання і знову потенційно досліджувати свій власний план.

  Завершений об'єднаний план приводить до розвитку зобов'язань між групою агентів, що взаємодіють. Врахування зобов'язань є ключем до успіху розподіленого планування. Коли об'єднаний план сформовано, кожен агент зберігає інформацію про зобов'язання, узяті на себе. Ця інформація включає дії, які будуть виконані, обмеження на ті дії, і кому агент  зобов’язаний виконати такі дії. Агенти використовують цю інформацію про зобов'язання, щоб підтримати повідомлення про завдання, визначаючи, кого повідомити, коли завершено спільне завдання або, чи оновлено план щодо спільного завдання. Оновлення плану містять у собі оновлення для того випадку, коли завдання перенесено, коли воно займає більше часу, ніж очікували, або коли агент вважатиме, що завдання зазнає невдачі. Зобов'язання також керують майбутнім місцевим плануванням. Якщо альтернативний план під час  розгляду вимагає порушення зобов'язання, корисність ухвалення такого плану має включати негативну корисність, що представляє вартість порушеного зобов'язання. Збереження недоторканості зобов'язань підтримує навколишнє середовище, де соціальні і глобально спрямовані дії мають велике значення і допомагає запобігти низці зламаних зобов'язань, якщо є високі рівні взаємозалежності агента і завдання. Це також не дозволяє агентам бути недальновидними, запобігає постійному переключанню планів у намаганні досягнути місцевих оптимумів.

  Можливо, що певні дії вимагатимуть паралельної взаємодії багатьох агентів під час виконання. Прикладом цього виду дії був би промінь мультиробота, що піднімається в домені конструкції [52]. У таких випадках протокол формування співпраці можна було б розширити, щоб відправити багаторазові запити в той же самий час до набору відповідних агентів.

  Процес вибору агента для співпраці можна здійснити багатьма способами і він є потенційною областю майбутнього дослідницького інтересу. Ідеально, коли б агенти вибрали того агента, який, за їх переконанням, найбільш здатний виконати це завдання. Доцільність могла бути визначена з попередніх взаємодій, моделей кредитоспроможності, знання поточних планів і завантаження інших агентів. Альтернативним і недорогим методом був би такий, який вибирає навмання такого агента з їх набору, який здатний виконати дане завдання. Це зменшило б обчислювальні витрати, коли в агента вимагають визначити відповідних співробітників, але, ймовірніше, це призведе до відхилень і триваліших періодів переговорів.

Щоб оцінити запит завдання, агент цікавиться визначенням того, чи було б виконання завдання корисним, враховуючи стан середовища, його соціальну філософію, поточний план і його графік. Динамічна мережа вирішення агента - механізм, який використовують для цієї оцінки. Мережа рішення визначає корисність дій, які базуються і на моделі наочної області агентів і на її філософських принципах, які відобразили на корисності. Щоб включити зовнішній запит завдання в DDN, змінну запиту можна встановити як істину в моделі наочної області агента. Наприклад, моделлю домену для агента, який може поставити каву і пошту, можуть бути вузли deliverCoffeeRequest і deliverMailRequest. Коли від зовнішнього агента отримано прохання доставити пошту отримане, агент може встановити це переконаня як істину. Насправді, це додає нову складову мети для агента. Тоді агент може вибрати дії високої корисності, щоб виконати їх за допомогою свого процесу планування. Якщо ці дії високої корисності задовольняють нову складову мети , агент має прийняти запропоноване завдання і оновити його поточний план з новим впорядковуванням дій високої корисності, які він згенерував. Проте, якщо недавно виконані дії – ті самі, що й у вихідному плані агента,  або не приносять значних успіхів у необхідному завданні, агент має відхилити пропозицію, оскільки виконання нового завдання тепер не  вигідне. Якщо в плані агента не з’являються належні дії для виконання завдання, агент не може виконати запит у майбутньому. Проте це не означає, що агент не міг виконати запит пізніше, але поза його діапазоном планування, агент занадто впевнений стосовно середовища, щоб спробувати передбачити його стан або корисність дій і передати будь-які дії. Альтернативно, агент може виконати дії, які досягають відповідного стану, але не під час тих самих обмеженнях, які запропонували спочатку. Якщо це відбувається, агент має відхиляти початкову пропозицію із зустрічною пропозицією, яка містить завдання і нові обмеження, де агент переконаний, що може виконати завдання. Якщо одне з обмежень на запропоноване завдання - обмеження крайнього терміну, агент має також виконати передбачення щодо часу, щоб виконати завдання. Враховуючи це передбачення, агент, у свою чергу, може запропонувати новий кінцевий термін для завдання. Після отримання зустрічної пропозиції контрагента може передбачити його очікувану корисність через DDN, враховуючи запропоновані обмеження зустрічної пропозиції. Якщо цей стан є прийнятним для контрагента, дозволяючи йому досягнути його власних цілей, то він приймає або відхиляє зустрічну пропозицію. Якщо контрагент відхиляє зустрічну пропозицію, йому слід спробувати повторно запланувати або знайти іншого агента для виконання завдання.