Agents on the Web

One of the key outcomes from this working group was a consensus on the importance of identifying a general representation format to enable both interoperability between different Multi-Agent System (MAS) implementations and adaptability to unexpected differences in the environment for agents that can engage in goal-oriented decision-making on the Web. In the first three days of the seminar, this working group focused on aligning the necessary terminology, investigating the definition of high-level goals, identifying different use cases and decision-making procedures, and establishing the required abstractions for supporting plan execution. On the fourth day, this working group further merged with working group 5 which was focusing on the synthesis of MAS, with a particular focus on strategy identification for agents on the Web. A brief summary of the broad range of topics discussed is provided in the following.

Early in the working group discussions, it became apparent that there was a divergence in the terminology used. This section outlines key terms along with definitions that were agreed by the group.

• $\mathrm{■}$

  Environment: Generally viewed as the space that an agent inhabits. Environments can be physical, virtual, or a combination of the two. In MAS, environments are seen as being first-class abstractions in that they are as important as the agents that inhabit them [2]. In this working group, given the scope of the seminar, the environment was considered to be a set of resources that are published on the Web; are accessible through the Web; and are linked to one another (where relevant) via hyperlinks. Those resources could relate to physical (e.g. sensors, actuators) or virtual (e.g. databases, services) resources.

• $\mathrm{■}$

  Workspace: In general, a workspace is part of an environment that is oriented towards a specific (set of) tasks or activities. Workspaces are an intermediary layer that adds structure and organisation to the environment. Agents typically operate across one or more workspaces. For the working group, a workspace was viewed as a set of resources that are somehow related (e.g. the resources relating to a smart room or building) and should be monitored by agents operating in that workspace.

• $\mathrm{■}$

  Situatedness: This refers to the relationship between an agent and its environment. Situated agents are able to interact with their environment via sensors and actuators. Situated agents are considered to be closely coupled to their environment, and their behaviours can often be defined in terms of their effect on the environment. In terms of the working group, agents are situated in the Web environment described above. Agents are able to identify resources through Uniform Resource Identifiers and are able to interact with them using HTTP operations.

• $\mathrm{■}$

  Artifact/Thing: Artifacts are an abstraction of the non-agent entities that exist within an environment. The concept arises from the Agents & Artifacts meta-model [2]. Artifacts typically adhere to a well-defined interface that can be used by agents. Artifacts can be anything (e.g. an diary, a shared whiteboard, or a web browser). In terms of the Web, one possible application of artifacts is to use them as abstractions of resources [3], providing a enabling medium for agent-resource interaction. In such an approach, the artifact would be responsible for exposing the state of the resource and providing the necessary functionality to interact with the resource. In contrast, a Thing is a specific type of environment entity; typically a physical sensor / actuator device. The term comes from the Internet of Things (IoT) community. One refinement of this view comes from the Web of Things (WoT) community, where things are exposed on the Web as a resource. Access to sensor data or control functions is exposed through the Web, and the interface is usually described by an associated Thing Description. In this sense, a Thing can be viewed as a stylised Web resource whose representations are constrained by agreed standards.

• $\mathrm{■}$

  Action/Operation: Agents perform actions in the environments they inhabit. They do so by invoking actuators that implement the primitive mechanisms for affecting the environment. Agents choose the action they wish to perform through a variety of approaches, such as stigmergy, reinforcement learning or symbolic (logical) reasoning. In the context of the working group, actions was taken to generally refer to the submission of HTTP Requests to Web resources. An Operation is a type of actuator that is associated with the Agents & Artifacts meta-model. It is part of the well-defined interface described earlier. Each artifact has an associated set of operations that represent the different ways that an agent can interact with the artifact. In terms of the working group, it was agreed that agents perform actions by invoking operations on artifacts. Further the set of operations associated with an artifact representing a Web resource would be the set of valid HTTP Requests that can be used with that resource.

• $\mathrm{■}$

  Effects/Pre-/Post-Conditions: In order for some types of agent to decide what action to perform next, they need a description of the context in which an action can be performed and possibly description of the impact/effect of that action. The terminology for describing these descriptions is commonly drawn from early work on planning and they are often defined in terms of logical formulae, but this is not a requirement. The context in which an action may be performed is often defined as a partial description of the state that the environment must be in for the action to be applicable. The action context is often defined as a set of pre-conditions that is part of an action description that also includes unique identifier for each action. In addition to providing a context in which the action is applicable, many action descriptions also provide additional information about the Effect of the action. This is often described in terms of the changes that the action makes to the environment (both addition and removal). Effects are also known as Post-conditions. The action descriptions are developed for specific scenarios as part of the domain model. In the context of this work package, pre- and post- conditions are expected to be defined in terms of the current state of one or more resources and the changes that a given HTTP Request will have on that (set of) resources. How to express a state of multiple web resources was not completely clear.

• $\mathrm{■}$

  Goals: A goal is generally viewed as a future state of affairs that the agent (or system) is trying to achieve. Achieving a goal involves the creation of a plan of action. A plan is a set of actions whose cumulative effect is the achieve the goal. The task of constructing a plan of action to achieve a goal is known as planning. Goals that identify future states that the agent wishes to achieve are broadly known as declarative goals. This type of goal contrasts with the idea of procedural goals – goals that encapsulate some behaviour that is to be achieved. For example, the task of paying a bill assigned to an agent can be expressed declaratively via the goal <paid bill> or procedurally via the goal <pay the bill>. The former refers to the state of having paid the bill and the later refers to the procedure of paying the bill. Generally, planning involves the use of declarative goals as it allows the planning problem to be expressed as a search through a space of possible states. States are represented as nodes, and actions are associated with edges that transition the system from one state (node) to another (node) as defined by the pre- and post- conditions of the action description. In terms of this working group, much of the discussion focused on goals in a more abstract sense or around declarative goals.

• $\mathrm{■}$

  Global Guidance: Global guidance refers to the creation of high-level plans to achieve domain specific goals. It is primarily concerned with goal refinement and is expected to utilise planning techniques in conjunction with any domain models that have been developed for the scenario. Largely, global guidance is concerned with the strategic decision-making activities of the deployed system. The idea of global guidance is refined further in section 5.3.4.

• $\mathrm{■}$

  Local Guidance: Local guidance refers to the refinement of high-level plans based on the context in which the agent is operating. It is primarily concerned with the reification of the abstract domain model derived plans with the actual configuration of the environment. In contrast with global guidance, local guidance is primarily concerned with tactical decision-making and is also discussed further in section 5.3.4.

• $\mathrm{■}$

  Protocols: Protocols define structured interactions between agents. They define a set of messages that should be sent between two or more agents with a specified ordering that can be global or partial in nature. Protocols are a building block for defining valid patterns of interaction between agents. In the context of this work package, the existence of protocols was assumed, but was not considered in detail.

• $\mathrm{■}$

  Organisation: In Multi-Agent Systems research, an organisation is broadly defined as a collection of agents that work together within an agreed context that is based around a set of well defined roles with clear lines of communication and responsibilities. Organisations apply structure to a Multi-Agent System and agents can play different roles within that structure at different times depending on their own goals and objectives. In the context of this working group, the function of an organisation was not discussed extensively.

• $\mathrm{■}$

  Norms: Norms define the standard behaviour of a system (e.g. all cars going in the same direction drive on the same side of the road). In societies, norms often emerge from the behaviour of the individuals within that society (everybody else is doing it, so should we). Norms can be formalised as laws, with an associated penalty, that can be used to enforce compliant behaviour. Like organisations, norms can be used to provide additional structure around the behaviour of agents. In some respect, norms can be seen as a less rigid than organisations because that provide a kind of social guidance that each agent can either adhere to or not. In the context of the working group, there was little discussion around the use of norms.

The provided definitions enabled us to discuss primary abstractions that are commonly encountered in a MAS. Such abstractions have been identified as potential candidates for representation in a common format towards facilitating the interoperability and adaptability of agents on the Web.

In this section, we present a scenario to motivate the definition and representation of proper abstractions to support agents’ interactions in hypermedia environments. Given that agents can execute a variety of tasks that call for coordination and communication among them, and that the group was interested in challenges posed by a real-world scenario with agents interacting through the Web with an evolving physical environment, a building automation scenario can provide a suitable environment for testing a concept for modelling abstractions of MAS.

In such a scenario, a human user may have a set of preferences relating to environmental conditions stored in a personal Solid Pod²⁹²⁹29https://solidproject.org. Agents in the MAS can use the data from the Pod to adopt goals towards increasing the user’s comfort with respect to the given set of preferences. In the most simple scenario, we can imagine having a single agent managing a room in the smart building, identifying users, retrieving information from the Pods of the identified users, and striving to implement the desired environmental preferences. Of course, the agent might also need to adapt its behavior based on constraints about energy consumption, or towards supporting users’ productivity or health and safety, and so on.

Given a generic specification of the user comfort level as a goal, the agent will be delegated to navigate the hypermedia environment and find the WoT Thing Descriptions of the things it can interact with and adjust the conditions accordingly. Table 1 lists some things and services the agent might need to interact with to achieve its goal.

Of course, there are other ways to implement this use case without having a single central agent capable of managing everything. We could for example have different personal agents representing different users, that will try to negotiate the best environmental condition for each user. For instance, for finding a common sense for different preferences of multiple human representative agents can adopt an existent protocol for auctions [1]. Also, an agent representing the room’s provider might be present, and have its own preferences (e.g. a certain threshold in energy consumption) in conflict with the comfort level thus they should be negotiated and prioritized according to some extra definitions.

Another possibility may be to also have multiple agents controlling certain room conditions. In each room there might be agents in charge of adjusting the temperature, humidity, and illumination of a room, then the task would no longer require an agent to navigate the hypermedia environment directly looking for things, but instead to navigate the MAS to find which agents are responsible and interact with them. For instance, if the current room temperature is not as a human prefers, its representative agent can ask the agent responsible for controlling the room temperature to adjust it accordingly.

When the room is occupied by more than one agent, the interactions and coordination issues can be even more complex. In this scenario setup, the agents can interact with each other to properly coordinate their actions over the things of the room.

To monitor and control things, and to negotiate a suitable condition for the room, the agents must employ common abstractions to describe their knowledge, intentions, goals, and plans. Table 2 shows possible interactions between agents and things and among agents, as well as necessary abstraction that they must share.

For this section, we assume that we already have a way of expressing goals for agents as well as actions, which agents can take, and their effects on the environment at an abstract level. We will call this a domain model. An example of an abstract representation of an agent’s goal in the domain of building automation would be “I want to make the room brighter”. The domain model would then comprise all possible actions and their effects, e.g. “I can set the power of light bulbs to adjust the brightness” or “I can lift the blinds of a window in order to adapt the brightness of the room to the outside brightness”.

Agents that want to achieve such a goal in hypermedia environments like the Web usually have to make plans on two different levels. We call them strategic planning and tactical planning. Strategic plans are plans on a high level of abstraction, and they are made a priori, have a global scope, and are based on a domain model (which could e.g. captured with an OWL ontology). A strategic plan in the given domain for the goal “I want to make the room brighter” could, for example, be “I need to find a light bulb in the room, then I can adjust its power”. We make no assumptions about the mechanics of the plan creation or acquisition here (it could be classical PDDL planning, but it could also be a neural network generating the plan).

To actually carry out a plan, an agent has to interact with its environment. In the case of hypermedia environments, these interactions usually are either following a link or submitting a form to a server. This means that agents have to refine their strategic plan to be able to execute it. Agents employ tactical planning to refine their strategic plans. Tactical plans, as opposed to strategic plans, are made at run time, have a local scope, and are based on what the agent found out about the environment (e.g. based on WoT Thing Descriptions that have been found). An example of a tactical plan would be “I send an HTTP POST request with the payload ‘<> rdf:value 10 .’ to http://ex.org/room1/bulb4/properties/power”. A comparison between strategic and tactical plans can be seen in Table 3.

We need the separation between the two levels of plans because hypermedia environments are usually highly dynamic environments and (strategic) plans that are too detailed get obsolete very fast.

The environment can help agents in creating tactical plans by providing metadata about the available links and forms that the agent can understand (e.g. “If you follow this link, you will get a list of all devices in the room”). The environment could even take a more active role in guiding an agent by presenting them only links and forms which the environment knows that they are useful to the agent (e.g. “I know you are an agent for handling the room brightness, thus I will only show you links to the devices that can influence brightness”).

What parts of a plan should belong to the tactical side and what to the strategic side is not fixed but lies on a continuum. The exact position on the continuum depends on the use application scenario. At one end of the continuum, plans in agents would be hard-coded: the agent already has a very detailed “strategic” plan of what exact steps to carry out in which order (first send this HTTP request, then that HTTP request) based on the domain model before it starts executing it. This works well in a static and deterministic environment, and it is very efficient there, but hard-coded plans are not flexible and cannot adapt to unforeseen changes in the environment at all.

On the other end of the continuum, agents do their best effort link following: the agent has no strategic plan at all (maybe because it does not have knowledge about the domain) and just follows the links and submits the forms that at the moment seem most useful to them; it just uses tactical plans. This approach is very flexible (as it makes no assumptions about the environment) but usually also not very efficient.

For the design of Hypermedia MAS, it clearly is a challenge for system designers to determine where on the described continuum the different agents should be located. It will also be important to find out, how the transitions between the two planning tactics work and how they influence each other.

The discussion about strategic and tactical planning presented in the previous section moved our focus from the external data that should be made available to the agent to the internal decision-making processes. We believe that a better understanding of the patterns that agents could use to reason and adapt to changes in their environment is crucial to also identifying how to sufficiently describe such environments with a suitable representation.

We then decided to join our efforts with the working group focused on synthesis in MAS since both groups shared an interest in the activities of the other and felt they were going towards similar objectives.

We ended up with a shared view of the main abstractions that are needed to design a MAS in order to account for many possible strategies to refine tactical planning. We named such strategies Course Check and Revision Strategies (CCRS) which are further described in our shared report.

Our initial focus on examining representation formats for describing goals and environments led us to explore ways to enable heterogeneous agents to collaborate effectively on the Web and to enhance agents’ autonomous decision-making through tactical planning. Eventually, we shifted our attention towards designing a system that accounts for divergences between the design time abstraction of an environment and its run-time implementation.

The collaboration between our team and the working group on the synthesis on MAS has proven to be fruitful. We are pleased with the outcomes of our joint efforts and intend to pursue this research direction further. Specifically, we aim to investigate the use of CCRS in agent architectures, and how these strategies can be supported by detailed descriptions of the hypermedia environment, the goals of a MAS, and the other agents present within the system.

This working group report sums up the activities of the joint sessions between working group 4 (Representation Formats) and working group 5 (MAS synthesis). The groups merged due to similar interests in the relationship of design-time plans and run-time adaptation to real hypermedia environment for autonomous software agents. An extended version of this work has been submitted to the 2023 ACM Hypertext Conference.

Supported by Web browsers and online services such as search engines and recommender systems, many people today excel at efficiently navigating the Web’s hypermedia structure towards achieving their goals. The essence of navigating hypermedia is that a user is able to match a discovered – local – hypermedia control with their – global – application goal. For instance, the control HTTP PUT /cart { ’’isbn’’ = ’’978-1452654126’’ } should be matched with the goal to buy the book “The Design of Everyday Things”). Users accomplish this matching using information in the representation of the current Web resource – in the above example, this might be a button labelled Add to Shopping Cart! or a cart icon. The user hence needs to be able to find out that a specific local hypermedia control is indeed suitable to advance towards their goal; for buying a book, this is true for most users because the online shop has been modelled according to how people shop in the physical world, hence it is natural that the book should be “put into the cart” for enabling the user to, eventually, buy it.

From a technical perspective, this process is on the Web enabled by a mechanism that is part of the Uniform Interface constraint of the REST architectural style [1]: Hypermedia as the Engine of Application State (HATEOAS) constrains REST systems so that clients only perform hypermedia state transitions on resources using actions that are provided within the hypermedia that the server delivers [2]. With HATEOAS the only implemented capability of a hypermedia client should be the way to select which hypermedia control is useful to achieve the goal. This avoids tight coupling between clients and servers, and permits a hypermedia environment and its clients to evolve independently from one another.

While central to the way humans navigate the Web, the REST HATEOAS constraint is today not emphasized in the design of hypermedia environments that are roamed by machines. However, following larger academic emphasis on this topic in the wake of the Web of Things movement [3, 4, 5], industry and standardization groups have been gaining interest in HATEOAS over the past decade, for instance at the World Wide Web Consortium’s (W3C) Web of Things (WoT) Working Group.³⁰³⁰30https://www.w3.org/WoT/wg/. This rising interest is driven by an increasing requirement on machine clients to more autonomously navigate hypermedia environments, and handle environment dynamics [6].

We argue that not least due to today’s wide availability of powerful AI models that might be used by artificial agents to provide guidance in hypermedia environments, revisiting the role of HATEOAS and the matching process of high-level domain goals of agents with low-level hypermedia controls is required. HATEOAS, together with suitable local traversal strategies, could form a cornerstone to permit artificial agents to roam the Web – and use its services – similar to how people do it.

In-line with research in the field of Autonomous Agents and MAS, we suppose that an artificial agent for a hypermedia environment is created by an agent designer according to a (design-time) model that the designer holds of the environment. This creation process involves the design and programming of the agent’s logic towards achieving the agent’s design objective. At run time, the agent is placed in a hypermedia environment and executes its programmed behavior. In environments such as the Web, it is however likely that the agent will encounter an environment that does not exactly match the expectations of the agent designer. The agent then either needs to cope with unexpected violations of the design-time assumptions (e.g., nonexistent hyperlinks or link relations); or it may optimize its way to achieve the goal if discovered hypermedia controls suggest better ways to achieve its design objective.

We argue that, to permit this level of adaptation to the environment, the agent should be equipped with strategies of evaluating which of a set of encountered hypermedia controls will enable it to realize its design objective.

We refer to such strategies as Course Check and Revision Strategies (CCRS). A CCRS describes what an agent does at run time to verify if the next step of its planned course of action is (still) possible and/or prudent given the available run-time information and the agent’s objective. From an application perspective, CCRS can be either reactive or proactive: Reactive CCRS are designed to enable agents to cope with unexpected variations of the run-time environment that violate design-time assumptions. The agent hence is required to deviate from the original course of action; for instance, the agent designer might not have known that an agent would need to be logged in to access a specific resource – the agent in this case requires a CCRS that permits it to discover how to log in to the system at run time. Proactive CCRS permit agents to discover opportunities that it may choose to exploit to achieve its design objective in a better (faster/cheaper/more privacy-friendly/etc.) way. Following these opportunities, the agent then actively changes its designed course of action to optimize the path towards its design objective.

When creating an agent to reach an objective in a hypermedia environment, the agent designer may then equip its agent not only with the primary (sometimes even hard-coded) course of action – e.g., a list of URIs to access; a list of link relations³¹³¹31https://www.iana.org/assignments/link-relations/link-relations.xhtml to follow; a list of W3C WoT Interaction Affordances³²³²32https://www.w3.org/TR/wot-thing-description11/ to exploit; etc. – but also with one or several CCRS among the ones presented below.

In this section, we propose a list of CCRS that an agent designer might select from when creating agents that roam Web hypermedia environments – or other environments where HATEOAS-like feedback is available. We do not claim that this list is exhaustive; rather, it should provide a starting point for the creation of a catalog of CCRS while at the same time further illustrating our approach and connecting it to different areas within artificial intelligence and beyond. The choice of a specific CCRS depends on the amount and type of autonomy and flexibility that an agent designer intends to give to the agent it creates as well as on the specific abstraction of the environment that the agent designer holds at design time.

We group CCRS in four categories: Independent, Environment-Oriented, AI-Oriented, and Socially-Oriented which are briefly illustrated in Table 4.

We provide a simple yet sufficiently complex scenario to illustrate our proposal and the interplay between the creation of an agent at design time and its execution at run time. For this scenario, suppose that a designer creates an agent that it intends to task with switching on a lamp in a hypermedia environment and then leaving feedback about its usage of the hypermedia environment. At design time, the designer holds expectations about several aspects of the to-be-encountered run-time environment, and each of these expectations is connected to a confidence:

E1:

The designer knows with full confidence that the environment’s entry point URI is https://mythings.example.org/room-d-12.

E2:

The designer knows that the entry point URI represents a thing directory, i.e. a list of hyperlinks to Web APIs of physical devices that are contained in a room. The designer is sure that there is only a single lamp in this list and believes that the hyperlink to the lamp’s API is located on the second page of the directory. While the designer neither knows the URI of that page nor of the lamp’s API, the designer believes that the directory exposes next link relations to support pagination.

E3:

It is unknown to the designer what specific lamp the agent will encounter at run time, and hence it does not know about the API. The designer furthermore does not know whether the agent will be required to first log in before it can switch the lamp.

E4:

The designer has high confidence that all hypermedia resources expose hypermedia controls for leaving textual feedback. The designer knows that the link relation that is exposed to hint at these controls is leaveFeedback and they know about the specific hypermedia control required.

The designer creates an agent to achieve the design objective based on this environment model: Based on (E1), it programs this agent to first send a GET request to https://mythings.example.org/room-d-12. Based on (E2), it programs the agent to, next, find a next link relation and follow it until the returned resource representation contains a hyperlink to the API of a Lamp. Based on (E3), it programs the agent to achieve the goal Lamp On which it specifies declaratively using a suitable language (e.g., RDF³³³³33https://www.w3.org/RDF/). Finally, based on (E4), the designer programs the agent to find a leaveFeedback link relation and use it to send a feedback text.

Because of its little knowledge or low confidence with respect to E2 and E3, the agent designer furthermore equips the agent with several CCRS to locally cope with deviations and/or optimize its traversal of the hypermedia environment:

• $\mathrm{■}$

  To cope with a resource not exhibiting the expected link relations in Step 2 and Step 4 of the process (i.e., next and leaveFeedback), the designer gives the agent an AI-Oriented CCRS like using a large language model for the ability to cope with unexpected vocabularies.

• $\mathrm{■}$

  For achieving the goal of switching on the lamp, the agent designer equips the agent with a CCRS that uses an AI planning system for locally computing a plan. At run time, this CCRS will succeed if suitable metadata is available, where typical planners require the pre- and post-conditions of using a hypermedia control to be specified; these can then be chained to lead the agent to achieve its goal.

• $\mathrm{■}$

  The agent designer knows that the planning strategy, while remaining a possibility, might fail for several reasons. For this reason, the designer includes another CCRS that uses uses Consultation/Delegation. The agent is hence programmed to contact a (hard-coded or locally discovered) resource – e.g., a specialized local lamp-switching agent or a human agent – when it requires help with achieving its goal of switching on the lamp.

When the agent now starts executing its program in the given hypermedia environment, it will engage none, any, or all its CCRS after each usage of a hypermedia control to possibly modify its future course of action. In this example, the CCRS depend on implicit or explicit environment support, e.g. on information being available about the environment for the Planning CCRS, and on other agents being present and capable for the Consulting/Delegation CCRS.

In this section, we investigate how our proposed type of increased local autonomy through CCRS impacts the behavior and design of a Multi-Agent System (MAS). In a MAS, several agents work towards the achievement of their individual goals [7]. The way these individual goals are related to each other defines whether the agents within the MAS are cooperative – in this case, a top-level goal is usually decomposed into smaller problems that are solved by agents that share results and communicate with each other. In a non-cooperative scenario, agents might have competing interests, but usually are expected to work rationally and towards achieving an equilibrium [8].

In our exploration we considered only a cooperative MAS expanding the scenario from Section 5.4.5 to one with two interdependent agents in two roles:

• $\mathrm{■}$

  The Lamp Operator is tasked to use hypermedia to turn on a lamp in a repository and then leave feedback.

• $\mathrm{■}$

  The Heater Operator is tasked to use hypermedia to turn on a heater and then leave feedback. It holds a key that, when submitted through HTTP POST to the https://mythings.example.org/authorizeAll endpoint, will authorize other agents to access the repository resource.

In this situation, the MAS designer will create a multi-agent plan that requires the Heater Operator to first post the key to unlock the repository, then access the repository, and then search for the heater hypermedia control and actuate the heater. The Lamp Operator agent will be programmed to wait until it can access the repository and then proceed to find and use the lamp control. In our approach, the MAS designer equips the two agents with suitable CCRS to permit them to recover from unexpected run-time situations and to identify optimization potential at run time.

However, suppose that, at run time, the Heater Operator uses a CCRS to discover that there is a direct access link to the heater control in the environment that permits it to access that control without first posting its key. Although it might be prudent for this individual agent to optimize its course of action, this behavior would not satisfy the goal of the MAS, since the Lamp Operator would in this case not be able to complete its design objective.

Societies of agents are constantly confronting a changing world, environment, and society. They have to learn how to behave in such a context and to reason on how to exploit what they have learned. Learning and reasoning connects well with the other topics discussed during this Seminar, in particular in connection with the following questions:

• $\mathrm{■}$

  How can we incorporate metadata about the data used for learning and reasoning, including metadata to determine its provenance and trustworthiness?

• $\mathrm{■}$

  How can we store and query the data needed for learning and reasoning in a decentralised manner, as in pods for individual agents?

• $\mathrm{■}$

  How can learning and reasoning methods accommodate models of actuators, including through affordances, in the design of an environment through which an agent can observe and control the environment?

• $\mathrm{■}$

  How can agents create and execute collaborative plans?

• $\mathrm{■}$

  How can agents interact with each other felicitously, through learning and reasoning about norms?

• $\mathrm{■}$

  How may flexible governance be accomplished by learning and reasoning about norms, especially to figure out the boundaries between competing norms in a contextual manner?

Because the topic is so wide, we choose to focus on one particular kind of objects: norms.

Norms are patterns of behaviour for group members in which compliance or violations of the implicit or explicit rules may lead to sanctioning. Norms vary in their extent of explicitness or implicitness and may be prescriptive (including proscriptive) or descriptive. Prescriptive norms may carry the force of legal regulations and laws. Sanctions may be positive or negative and may apply to an individual or a group and be given by an individual or a group [3]. One example is for drivers of vehicles on public roads, self-driving vehicles and humans, who will all need to follow the same norms to get along smoothly. Some of these norms are explicitly described in the highway code, whilst others remaining implicit, or tacit, must be learned through experience. Sanctions may involve honking the horn or flashing the vehicle’s headlights – besides actual fines for violating prescriptive norms, not solely descriptive ones.

On the web, where people and software agents meet, they both have to follow social norms. It is therefore interesting to consider groups involving combinations of people and agents. The agents are intelligent provided they can learn and reason as they interact with their environment, which includes other group members. Reasoning involves making decisions about actions with the environment, or changing the agent’s beliefs, desires, and intentions. Beliefs may also cover the agent’s understanding of people and other agents (as in the Theory of Mind modelling).

Some questions that arise:

• $\mathrm{■}$

  What is the relationship between norms and governance?

• $\mathrm{■}$

  Are we using agents to model people or are we investigating social norms for artificial agents?

• $\mathrm{■}$

  What are suitable metamodels for explicit norms?

• $\mathrm{■}$

  How can we describe behaviours in a symbolic or sub-symbolic form (e.g. using deep neural networks or other embedding techniques)?

• $\mathrm{■}$

  How do we revise or update the rules of individual agents that describe their behaviour?

• $\mathrm{■}$

  How can we model heterogeneous communities of agents with different social values?

• $\mathrm{■}$

  How can we avoid unfair norms that are discriminatory to certain classes of users and agents?

• $\mathrm{■}$

  How can we deal with hostile or malicious agents?

• $\mathrm{■}$

  How are agents supposed to know and learn explicit and tacit norms?

• $\mathrm{■}$

  How can we evaluate the effectiveness of learning social norms?

One approach to learning social norms uses multi-agent reinforcement learning based upon (negative) sanctioning, where an agent, or a group of agents, makes known its disapproval of another agent, based upon the second agent’s behaviour. The disapproval could be communicated one-to-one to the agent deemed to have violated the norms, or publicly to the group as a whole.

We chose use cases that make the connection, at least in some respects, with agents and the web but require learning and reasoning. They show the practical use of the following aspects:

• $\mathrm{■}$

  Understanding the benefit of incorporating norms with respect to agents on the Web

• $\mathrm{■}$

  Learning, revising, and reasoning about behavioural norms

• $\mathrm{■}$

  Working with implicit and explicit norms

• $\mathrm{■}$

  Supporting norms in relation to planning tasks

• $\mathrm{■}$

  Supporting norms in relation to causal reasoning – understanding intent on the basis that most people/agents will follow the norm, and recognising violations

The use cases that we considered were as follows:

• $\mathrm{■}$

  Ride sharing across town balancing personal desires and needs, following norms, as well as continual learning of norms and related metadata

• $\mathrm{■}$

  Social media assistant advising you (in a dialogue) whether you would violate the norms should you go ahead and send your draft post, and/or for directing posts to moderators for possible sanctions. This is in the context of federated social networks such as Mastodon.

• $\mathrm{■}$

  Checking compliance with regulations such as GDPR and determining how they should evolve to reduce violations [2]: tighter or looser?

The ride-sharing use case is as follows: volunteers or paid drivers offer to drive people across town, e.g. to shops, medical appointments, and so on [1]. A car may be shared by multiple passengers with different pick-up and drop-off locations. Some people may be limited in how far they can walk. What are the rewards for the drivers to drive and for the passengers to accommodate each other’s needs? How can software learn metadata, norms, and sanctions from the journeys undertaken? How can we match drivers to passengers dynamically? How can we integrate with information sources providing the essential live or static knowledge, e.g. about roadwork? The people who want a ride should be able to offer suggestions and express their preferences regarding the origin, destination, and timing of their journey.

What is the contribution of plausible knowledge and statistical models? How can we unite such knowledge with argumentation theory for assessing and balancing conflicting desires and constraints? How can we employ other approaches, e.g. constraint satisfaction algorithms, to facilitate smooth functioning and collaboration?

What kinds of norms arise in this use case? For example, a societal objective would be that the elderly or people with walking sticks should be dropped off close to their destination, and likewise picked up close to their starting points. Journey times should not be unreasonably long for any passenger. Journeys should be navigated to avoid known problems (road works, traffic jams).

How can this use case be implemented in a decentralised manner, where the information belonging to different users stays with them and in their control and where their decision making is likewise local?

We identified the following challenges and places for design decisions.

• $\mathrm{■}$

  Should the treatment of norms be data-driven or model-driven? We expect both in various ways but capturing their interplay is non-trivial.

• $\mathrm{■}$

  What are the tradeoffs between tacit and explicit norms?

• $\mathrm{■}$

  What are suitable standards for expressing explicit norms as a basis for reasoning about norms and the decisions to take in reference to the norms?

• $\mathrm{■}$

  How can agents incorporate Theory of Mind reasoning, involving beliefs, desires, and intentions (BDI) and other folk psychological notions?

• $\mathrm{■}$

  How can agents collectively learn norms in a federated manner without revealing confidential information of their users to others?

• $\mathrm{■}$

  How can learning and reasoning about norms be performed at the subsymbolic level?

• $\mathrm{■}$

  What are constraints on agent-to-agent communications, e.g., those that affect the learning performed individually and jointly by the agents?

• $\mathrm{■}$

  What would be the nature of an approach based upon publicly sharing information on norm violations, with such information sharing improving reasoning and acting as a potential deterrent to violators?

• $\mathrm{■}$

  How does learning and reasoning about norms relate to trust and trustworthiness, and provide a foundation for the construction of trustworthy systems? Agents should learn to behave in a trustworthy manner and should learn to calibrate their trust in another agent with its observed trustworthiness.

Enabling agents to learn and reason about behavioural norms will be increasingly important given the rapid pace of advances in artificial intelligence, and the need to ensure that applications enrich human society. This raises many challenging issues that we only had the opportunity to skim through in this report.

There are major similarities in the motivations behind multiagent systems (MAS) and the Web. Both disciplines and practices seek to advance decentralization and openness in that ideally there is not a single locus of control and agents can behave and interact broadly autonomously under local control.

This report addresses the interplay of multiagent systems with the Web. Specifically, it concerns how constructs and techniques identified in the study of the governance of MAS can be realized over the Web architecture and how the governance of the Web can be beneficially structured based on constructs and techniques developed for the governance of MAS. In simple terms, it seeks to answer the following two questions:

• $\mathrm{■}$

  What does the Web offer to support the governance of MAS?

  We anticipate ways to use the scalability and evolvability of the Web to build easy-to-use, widely deployed MAS. Scalability and evolvability are two of the several non-functional requirements that can easily be met if a system’s architecture relies on the Web.

• $\mathrm{■}$

  What does the governance of MAS offer the Web?

  We anticipate approaches for governance that provide flexibility and local control with formal models that support correctness and generality going beyond the typically procedural kinds of governance seen on the Web today. A challenge here is to map abstract models for governance in MAS to Web components, in a way that preserves Web architectural constraints and thereby guarantees the associated non-functional requirements of scalability and evolvability.

The main contribution of this report is the identification of crucial challenges pertaining to the interplay of MAS and the Web, and the formulation of some initial research questions that might guide future research on this topic.

We understand the Web as a collection of resources, identified with uniform resource identifiers (URIs) and supporting hyperlinked representations, along with a computational architecture that supports locating and accessing the identified resources. The computational architecture is based on standard protocols for manipulating resources (e.g., HTTP, CoAP³⁴³⁴34Constrained Application Protocol: https://datatracker.ietf.org/doc/html/rfc7252). We think here of architectural constraints (such as for caching, layering, and uniform interaction) as captured in the original design rationale for the Web Architecture [18], but see also the W3C Recommendation for the Web Architecture [22]. Some of these constraints, especially uniform interaction, are captured by the Linked Data principles [21], which can be supplemented by an ontology specification [34]. Some extensions to the above architecture, such as through the observer pattern (implemented in CoAP [28]) and local state transfer [30], aim at going beyond the “Web of Documents” [19].

There are numerous studies relating the Web and MAS. These exhibit two general trends: some focus on applying RDF and Linked Data to expose agents to hypermedia-driven environments [4, 10, 16, 25], while others combine a formal declarative model of norms [7, 12, 26, 31] to specify social protocols [8]. Such social protocols provide a more thoroughly decentralized conception of Berners-Lee’s [1] notion of social machines. Recent W3C Recommendations for the Social Web, including Linked Data Notifications, ActivityStream, ActivityPub and WebSub [20], offer ways to connect these two trends, by implementing social protocols over Linked Data.

Dimensions that are common to all MAS architecture, such as the environment, organization and interaction dimensions, are defined at a higher level of abstraction than Web resources and protocols. Constraints such as caching, layering and uniform interaction apply to components, exposing a certain functionality through ports. Web components may only have client or server ports, exchanging messages in a standard protocol. Components with client ports only are called origin clients, those with server ports only are origin servers and a third kind of component, proxies, have an equal number of client ports and server ports, forwarding requests from clients to servers or vice versa [18].

To be able to analyse the interplay between MAS and the Web, a mapping from MAS abstractions to (more concrete) Web components is necessary. Given the complexity of both fields, there is no trivial mapping and most likely not a unique mapping across the two levels of abstraction. In the following, we perform a case study to help identify some preliminary mappings that would transfer effective governance mechanisms developed in MAS research.

Consider a simplified version of the process for allocating donated organs and tissue to potential transplant recipients called Carrel [33]. The distribution of organs and tissues in Carrel, given its Spanish and Catalan context, would be overseen by the Spanish ONT, together with the Catalan Organitzaciò CATalana de Trasplantament (OCATT)³⁵³⁵35https://trasplantaments.gencat.cat.

Tissue distribution is essentially demand-driven because tissues can be preserved and stored over extended periods with no significant degradation. Organ distribution is essentially supply-driven because the need is known before a suitable part becomes available. For the purposes of this report, we only consider the second case of organ distribution where the need is known before availability.

To achieve its goal, the requesting agent must negotiate with the agents that represent hospitals with potential donors. In the original version of Carrel, participating agents are in effect regimented by so-called governor agents, to prevent non-compliance, but in general, agents may choose to take non-compliant actions. Thus, we assume that agent actions in this contemporary Carrel are all visible to the regulatory bodies, as is the case in the physical world: hospital Transplant Coordination Unit agents (TCUs) communicate their requests to members of ONT/OCATT, who then contact other hospitals to find a donor and select the best match. To participate in Carrel, each agent must hold an authorisation in the form of a certificate.

We briefly highlight some relevant multiagent systems approaches.

On the Web, servers hold the power and may hide information, redirect requests or reject them, thereby reducing the action available to agents. We may think of institutions as components with a server port, receiving requests from agents Unlike a “user agent” (browser) in the Web architecture, an autonomous agent might have both client and server roles simultaneously and can have one-sided elementary interactions, where they are not awaiting a response. The requirements of autonomous agents are closer to those of servients in the lingo of the W3C Web of Things Architecture [24], which are components with both client and server roles that can interact in a peer-to-peer manner. If the agent is visible to other agents, i.e. if its representation is dereferenceable, the representation can point, for instance, to a Linked Data Notification inbox that receives messages from other agents [3].

An institution may not need to materialize as a Web component: if norms are defined at design time, agents may be guaranteed to behave (in general) as per these norms, and certification may occur at design time, such that an agent either uses a single certificate throughout the system’s lifetime or periodically renews its certificate. Such an institution would have no sanctioning power, nor any need for sanctioning. It cannot easily change the applicable norms either. Updating a norm would potentially require modifying the behavior of all agents at the same time. This is a basic, but inflexible solution.

Hypermedia-driven interaction can support autonomous agents to interact with Web resources in a uniform way while being decoupled from the underlying components. To illustrate how this works, an HTML page typically provides the user with a number of actions, such as clicking a hyperlink or submitting a form. Performing any such action transitions the user to a new page and exposes a new set of possible actions. In each step, the user’s browser retrieves not only an HTML representation of the current page from a server but also the hypermedia controls required to transition to new pages. Hypermedia-driven interaction reduces coupling between components (e.g., browsers, proxies, origin servers) and allows them to evolve independently from one another; a central feature that allowed the Web to scale up to the size of the Internet.

In the present case, the various actions – retrieving formal specifications of norms, requesting a certificate, or sending messages to other agents – can be made available to the agents through hypermedia controls. Such hypermedia controls would encapsulate all the information required by an agent to interact with the institution, but to use the hypermedia controls in a reliable manner the agent would have to operate on an abstract model of the institution. For example, if an agent is required to obtain a certificate at run time to enact an Organ Donation protocol, the agent could discover such an action possibility through hypermedia.

The institutional model could evolve throughout the agents’ lifetimes: for example, from using norms and certificates defined at design time to a model based on evolving norms [27] and certificates to be obtained at run time. Such an evolution would be reflected in the hypermedia environment through the action possibilities provided to agents at run time and thus, to cope with this evolution, the agents would adapt to a new course of action that meets their objectives. Some related work investigates the design of agents able to plan and adapt to dynamic hypermedia environments (e.g., see [11, 23]).

The contribution of this report is in identifying some new research questions that can motivate research on the interface of MAS and Web architectures. Specifically, we propose the following:

1. 1.

   How should we model the presence of a governance layer in a MAS?

2. 2.

   What aspects of a web-based deployment of a MAS may be subject to governance policies and included in an institutional environment?

3. 3.

   How do we map the required properties of an institutional environment (monitoring, reasoning, sanctioning power) to constraints and mechanisms of a web-based deployment and more specifically to hypermedia controls?

4. 4.

   How can we specify and implement composed and stacked agent environments (e.g. institutional environments that overlay physical ones and institutional environments that extend others)?

5. 5.

   Can and should a governed MAS on the Web be modelled and implemented as a hypermedia application?

Thinking about MAS and the Web together opens up new opportunities in building large-scale sociotechnical systems. Such systems would take advantage of the flexibility derived from MAS and the scalability and familiarity (to most developers) derived from the Web. The possibilities are promising and we invite the research community to join us in investigating them.

Agents are often challenging to test due to their complexity and the unpredictability and dynamism of the environments in which they are situated. It is considered infeasible to test all courses of actions that complex agents can take [1, 2]. Even for one particular goal, agents may have several alternative plans or may apply non-deterministic approaches, for example in the context of data-driven methods such as machine learning. In addition, testing stochastic scenarios and situations that entail interaction with other agents and humans can be challenging to reproduce and control [3, 4]. Ensuring that an agent behaves as desired in a relatively friendly environment is already challenging; assuring this at a scale that includes numerous autonomous software artifacts running relatively freely in the environment is a crucial problem [2].

For the specific case of agents on the Web, it is important to consider the Web as the decentralized environment where interactions happen, rendering the governance of agent on the Web a key challenge [5]. Interactions can take places between hetreogenous agents (e.g., using usual agent communication languages) but also between agents and other Web entities, applying various of actuators and sensors. We consider the case where the agent environment is identified by a set of resources that are published and made accessible on the Web. While these resources can be linked to real entities, like sensors, robots, actuators, drones, or smart devices, they can also be linked to virtual entities and services. The situatedness of these agents is an integral part of the Web environment, where resources and other agents are identified and located through URIs.

This chapter reports the main results of the working group “Benchmark and Testbeds”, as discussed during the Dagstuhl Seminar “Agents on the Web”. The different challenges regarding testing and benchmarking of agents on the Web were discussed, and specific scenarios and scenarios types for testing and benchmarking were proposed. Through the proposed set of scenarios and scenario types, we identified potential future work regarding the conception and implementation of testbeds for Web Agents.

The Web provides numerous opportunities for the use of agents and multi-agent systems that are diverse with respect to use cases and underlying technology stacks. In this section we introduce a list of categories of scenario types that can be used for testing and benchmarking MAS on the Web. We assess the scenario categories in terms of how easy (if possible) it is to apply techniques for testing autonomous software artifacts, such as unit, integration, regression, stress, and beta testing, and how to benchmark different application development approaches. A comparison of the categories considering their strengths and weaknesses is provided in Table 5.

The first scenario categories is based on legacy Web-based applications used in a “production-like” environment, i.e. in an environment that reflects the socio-technical complexity of a system whose operation has critical real-world implications, for example in a business context. The actual environment, which can be virtual or physical, is the “real-world” setting in which applications and devices are operating. Because each system has a distinct set of requirements and constraints, throughout the years several protocols (e.g.: CORBA, OPC, RPC) and architectural styles (e.g.: SOAP, REST, GraphQL) were adopted [6]. Legacy Web-based applications are usually a composition of different technologies that are integrated into a functionally somewhat coherent and cohesive system of high technological heterogeneity. Besides the lack of standardization, legacy web-based applications often have many human-machine interfaces of different maturity levels and frequently systems are hard-wired to each other via system actions on graphical user interfaces (in the case of so-called robotic process automation). Navigating this interface heterogeneity can be a key challenge for agents on the (current) Web. Another characteristic is that such applications have little space for mistakes when deploying new versions since they are usually in day-by-day usage by many users and often perform business-critical transactions. Examples of legacy web-based applications are: ERP systems, industrial automation plants [7] and digital marketplaces. One advantage of adopting this scenario category is that it exposes the system under test to a realistic environment which can facilitate software maturity and resilience, in particular because it reflects real-world requirements and performance indicators, allowing for meaningful benchmarking of the current system as well as of partial or full replacements that are technologically more advanced.

The third scenario category is based on simulated environments. Simulated environments can provide reasonably realistic constraints and intuitive visual interfaces for many scenarios. They are often built using simulation frameworks such as Gazebo³⁶³⁶36Gazebo is available at https://gazebosim.org/ and Morse³⁷³⁷37Morse is available at http://morse-simulator.github.io/ which provide tooling for applying physical constraints, and for drawing and animating representations of the environment, thus facilitating human interpretability. Such frameworks also provide tools for monitoring and debugging systems. There are many possible scenarios that can be simulated, such as transportation and search-and-rescue scenarios. As the scenarios can be simpler than the actual environment, simulated environments can facilitate the development of applications. However, the application is not exposed to all situations that can potentially occur in the real world.

Another scenario category are programming competitions, such as MAPC³⁸³⁸38More information about the MAPC can be found at https://multiagentcontest.org/ and RoboCup³⁹³⁹39More information about the RoboCup can be found at https://www.robocup.org/. These competitions provide different scenarios that can run either simulated or real-world environments. A distinguishing characteristic of this scenario category is that in order to facilitate competition, the scenarios have well-defined performance indicators, which enables the comparison of the different approaches.

Finally, there are scenarios provided as testbeds. Testbeds are defined for experimenting and comparing approaches [8]. For instance, a scenario may allow agents to enter buildings and rooms therein in order to interact with appliances such as light switches, which in turn affects the state of the environment. This scenario shares characteristics of simulated and competition scenarios as it is defined for a small set of actions; it is not supposed to be in use in production, and its performance requirements and indicators can be easily defined and monitored. Ideally, testbeds share some of their characteristics with production-like scenarios as they are usually developed using real devices and run in a (potentially cyber-physical) realistic environment. In the context of the WoT, due to the lack of existing simulated and contest scenarios and limited access to WoT scenarios in real-world environments, testbeds can provide ideal conditions for testing and benchmarking MAS on the Web.

In this section, we propose a synthesis of technical terms of related to the engineering of agents & MAS and existing standards and practices from the Web.

Envisioned and existing agents on the Web perform tasks on different levels of interaction with the environment and other agents, which can get categorized into:

1. 1.

   Data Gathering – such agents crawl the web in order to gather information, and may exhibit a querying interface. That is, they operate in read-only mode with safe HTTP requests.

2. 2.

   Actuation – such agents may also read information, but their characteristic is that they additionally perform writing operations on the environment using unsafe HTTP requests.

3. 3.

   Communication – such agents engage in conversation with other agents. To this end, they also perform writing operations, but to specific endpoints of other agents, with the goal of communicating.

Note that in the context of testing and benchmarking, in order to provide means for comparing approaches and MAS applications, the focus is “top-level goals rather than approach-specific goals” [9].

In order to combine MAS and Web approaches, a common view on what can constitute agenthood on the Web needs to be established. Depending on the above interaction levels for agents, it is especially on level 3, where the following aspects are required:

• $\mathrm{■}$

  Identity – an agent needs an identifier, i.e., a URI on the Web.

• $\mathrm{■}$

  Endpoint – an agent needs a way to receive communication, e.g., an LDN inbox.

• $\mathrm{■}$

  Entry point – an agent needs a way to expose information, e.g., an FOAF profile document on the Web.

The other levels 1 and 2 require other aspects:

• $\mathrm{■}$

  Situatedness – the agent needs a reference to where it is. On the Web, this could be a (set of) seed URI(s) for a data gathering agent; or an actuating agent could be constrained in its behavior using a query.

• $\mathrm{■}$

  Norms – to formulate desired agent behavior using norms, a notion of norms for the Web needs to be established. This could be implemented as agent behavior descriptions, for which there are no standards and practices yet.

• $\mathrm{■}$

  Signifiers / possible actions – for an agent to find out what it may do in an environment, descriptions of actuable items are required; on the Web there are, e.g.  schema:PotentialAction, which represents a coarse match to the agent terminology.

• $\mathrm{■}$

  Adaptivity – an adaptive agent can act in different environments. On the Web this may mean that the agent leverages reasoning to deal with heterogeneous descriptions.

With those proposed translations, the following steps may need to be taken to run, test, and benchmark agents:

• $\mathrm{■}$

  Define very simple norms – with the notion of behavior hardly defined for the web, simple condition-action rules may be used to implement a very simple norm.

• $\mathrm{■}$

  Analyze norm and policy compliance – here, log analysis techniques may come in, corresponding metrics need to be defined.

• $\mathrm{■}$

  Enact norm violation punishment – depending on the scenario and the control over the environment, it may be possible to punish agents.

Testing and benchmarking are cornerstones of modern software engineering. Still, both topics receive relatively little attention in the context of the (engineering) multi-agent systems research. As reliable and trustworthy behavior is both particularly important and challenging when it comes to Web-scale systems, the research need around testing and benchmarking is even more pronounced here. Some of the open questions that future work can address are the following:

• $\mathrm{■}$

  Which abstractions are central to testing and benchmarking of MAS on the Web?

• $\mathrm{■}$

  What are good practices and pitfalls of Web-scale benchmarking of MAS?

• $\mathrm{■}$

  Does testing MAS on the Web require dedicated tooling support?

Initial works towards the implementation of a benchmark framework for testing Agents on the Web have started to emerge, as in the BOLD server⁴⁰⁴⁰40Bold Benchmark: https://github.com/bold-benchmark. Future developments and extensions to this type of framework may be a promising starting point for facilitating norm-based validation, agent behavior testing, assurance of policy compliance, and other aspects as discussed above. This working group has concluded that providing testbed environments such as the ones suggested in this chapter can potentially facilitate the systematic evaluation of approaches to engineering agents on the Web and to place a greater focus on the assurance of quality and reliability.