14.1 Introduction

The rapid growth of the Internet of Things (IoT) (Columbus, 2017) has created fertile ground for emerging research on a variety of existing and novel problems, such as privacy, cyber security, big data, and self-adaptation/self-organization. A single IoT device (e.g., a thermostat) may serve a particular purpose, but the conglomeration of multiple devices to serve a human, or a virtual entity’s global objective, is the true promise of IoT. The vision of pervasive or ubiquitous computing is the existence of computational middleware that discovers, and utilizes, a set of IoT resources so that they constructively cooperate with each other in order to achieve an identified global objective.

We note that this global objective, or objective for short, can be as simple as assisting a homemaker in the shopping and preparation of family meals, or as complex as a dynamic medical sensor network assisting in the care of hundreds, or thousands, of patients. An inherent challenge of IoT is that computational entities must operate in a highly dynamic environment, interacting with emergent phenomena that continuously change context, and may do so in unpredictable ways. Existing software-design paradigms cannot address many of these problems because they approach the bounds of the complexity manageable by a human designer. Existing software paradigms need to be extended, and possibly new ones created, to deal with the complexity brought about by the rise of self-organizing, adaptive, multi-agent systems (MAS, Bernon, Chevrier, Hilaire, et al., 2006, Bernon, Camps, Gleizes, et al., 2004, Gardelli, Viroli, Casadei, et al., 2006, Gleizes, Camps, George, et al., 2007).

Mihailescu, Spalazzese, and Davidsson (2017) introduce the idea of emergent configurations (EC) for an IoT driven by user requirements. The idea is to dynamically orchestrate heterogeneous “things” in a manner that enables goal-directed behavior in support of a user’s requirements. In this chapter we explore the idea of online agent creation and deployment as a way to realize an EC. In the context of our work, meta-agents are agents in a multi-agent software paradigm that utilizes reasoning to both construct and deploy special-purpose agents that form an EC. Unfortunately, but opportunistically research-wise, reasoning models that can support the idea of meta-agents in the context of an EC have not been explored. To realize an EC using meta-agents we need to first manage the complexity of the problem, then develop a multi-agent framework capable of supporting meta-agents, and, finally, explore reasoning models, such as belief-desire-intention (BDI) modeling (Georgeff, Pell, Pollack, Tambe, & Wooldridge, 1999), for autonomous meta-agents.

14.2 Managing Complexity

In his seminal work, The Sciences of the Artificial (Simon, 1990; see also Valckenars, Brussell, & Holvet, 2008), Simon explores the laws that bound artificial systems; in essence, he tries to develop a corollary to the laws of physics, but applied to artificial systems. In this work Simon outlines three assumptions that, when they hold true, require that any successful artificial system be holonic; systems characterized by a pyramidal structure. Simon’s first assumption is that of bounded rationality. Intelligent systems have a bounded, or limited, capacity for computation and communication. As the limits of that capacity are approached, adding more resources (faster computers, high bandwidth communication) produces diminishing returns. The implication is that real-world intelligent systems must be able to make decisions based on imperfect information and limited computations. Simon’s second assumption is that intelligent systems will operate in demanding environments. Intelligent systems must address nontrivial problems, make effective use of the resources available to them, and grow in complexity only in service of achieving a successful outcome. Systems that cannot do this will invariably fail and be replaced by more successful systems. Simon’s final assumption is that intelligent systems must be able to operate in a dynamic environment. Operating in a highly dynamic environment requires that systems have the capacity to quickly evolve to adapt to changing contexts. This requirement has implications for the idea of optimality. In a fast-changing environment the time required to design and develop a solution that approaches optimality makes a system obsolete before it can be deployed. Developing optimal systems has been the holy grail of computer science since its inception. Forgoing that goal in service of agility requires a major shift in thinking.

It is not difficult to show that meta agent-based emergent configuration systems are beholden to Simon’s three assumptions. First, meta-agent EC systems using IoT sensors and devices as their source of information will have to contend with operating in the computationally limited environments available on IoT devices. They will also have to operate with low bandwidth, disconnected (denied), interrupted, and latent (“DIL”) network connectivity (Scott, Refaei, & Macker, 2011). Second, these systems must solve complex problems by selecting the most valuable source of information out of hundreds of millions or billions of IoT information sources and perform the necessary reasoning given their limited resources. Finally, they will need to aggregate that information at higher levels of the pyramid into actionable information that addresses the current goal. This must occur in near real time and produce added value. There are many examples of such systems that address similar problems in well-defined domains, with a limited, well-defined set of sensors (Blum, 2011). We will address the difficulties in generalizing this problem later in the chapter.

14.3 Sentry AGEnts

The foundation of our work with multi-agent EC systems is based on a multi-agent system developed at the Naval Research Laboratory called Sentry AGEnts (SAGE). SAGE (Fouad, Gilliam, Guleyupoglu, & Russell, 2017) was initially developed to deal with the issues of online agent generation from data used in automating the testing of service oriented architecture (SOA) systems. SOA systems present a unique challenge for automated testing as they consist of systems of systems and, hence, traditional single-application test technology is insufficient. Automating an evaluation of SOA systems requires a distributed set of agents residing at each service provider or consumer and coordinating with other agents to simulate the complex, interdependent interactions that occur between users and consumers of SOA services (Fig. 14.1).

SAGE is a multi-agent system written in C ++. Its salient features include the ability for external systems, as well as SAGE agents, to spawn other or new agents online by dynamically populating their behavior modules and defining their state space. SAGE uses a very low overhead remote method invocation (RMI) mechanism that provides synchronous and asynchronous call semantics, serialization, as well as multithreaded execution on the server side. The advantage of using SAGE is that it has a very small footprint in both computational resource as well as network bandwidth utilization. Fig. 14.2 illustrates the SAGE architecture. One thing to note is that SAGE-agent execution is managed at each node of the network by a SAGE node process that acts as an agent virtual machine. One or more SAGE nodes can run at each network node. The SAGE server provides SAGE nodes with services, such as node and agent introspection, interagent communication and synchronization, and a repository of agent behaviors that can be used to construct new agents (Fig. 14.2).

14.4 An Illustrative Example

Artificial intelligence research is often conducted using toy problems that are simplistic but allow researchers to explore a problem space. In automatic path-planning research the game Frogger is an often-used toy problem (Frogger, 1981). The object of the game is to manipulate a frog character until it moves across a busy, multilane highway with cars traveling in multiple lanes of traffic at various velocities and in different directions, all the while avoiding being run over. Once that goal is achieved the frog character must then navigate across a river by stepping across floating logs, as well as other objects (turtles), that rise above the water for a short time.

As in much of path-planning research the goal is to find an optimal path that preserves the frog’s life given a priori knowledge of car behaviors. The problem is usually limited to the single task of crossing the highway because the second task of crossing a river requires a significantly different strategy. The algorithms generally do not generalize to be able to address both challenges (Fig. 14.3).

Our aim was to use Frogger as a toy problem for examining the utility of using multi agent–based emergent configurations to find optimal paths that allow the frog to cross both the highway as well as the river in real time with no a priori knowledge of either the location of the cars or the floating objects. We also wanted the same algorithm to be able to guide the frog across both the highway and the river by building specialized agent networks to solve each component of the problem.

The only input to our system is the state of sensors that monitor the environment. We modified an open-source Frogger implementation developed by Pavlenko (2009) to include road sensors on the highway that monitored a portion of a highway lane and returned a Boolean occupied/not occupied signal. In the case of the river, the sensors monitored the state of a portion of a water lane and returned a Boolean result indicating whether or not an object was available above the surface (Fig. 14.1). The Frogger game was essentially instrumented so SAGE agents could query the state of a sensor dynamically in real time. The placement of the sensors was clearly significant for they acted as sampling points. In order to guarantee that we had sufficient sensors so that the presence of an instance of a car as well as floating objects was never missed, we based our placement on the Nyquist Theorem. Specifically, we placed sensors along the highway and river at intervals that were half the width of the smallest object expected to occupy a highway or river lane.

To utilize an emergent configuration as a holonic system we began by creating a top-level agent to represent the frog in the Frogger game. We aptly name this agent Frog. The Frog agent has a single mission: to cross both the highway and river and emerge unscathed. To achieve this the Frog agent creates an oracle agent that informs it whether or not moving in any of the four allowed directions (north, south, east, west) is feasible. The oracle agent disallows a move either because it is illegal (e.g., moving south when the frog is at its start position), or because it would result in the Frog agent getting hit by a car, or sinking in the river. The Frog agent utilizes this information to reason about what its next move is to make. The oracle agent in turn creates one of two types of agents based on the current location of the Frog agent. Highway lane agents monitor the car traffic in a lane and inform the oracle whether or not a position on a highway lane is occupied and, if vacant, how long it can be expected to be vacant based on the velocity of the cars in that lane. The other type of agent is a river lane agent that informs the oracle whether or not a position in a river lane contains a floating object. Moving down the hierarchy, both types of lane agents create sensor agents, one for each sensor in the game, to monitor the state of the sensors and to return their current state to the lane agents.

At the start of the game only a single agent, Frog, exists. The Frog agent is aware that it must accomplish two different tasks that require different types of information. The agent first creates a network of oracle, lane, and sensor agents to enable it to cross the highway. Once that goal is achieved, it destroys that network and creates a new agent network that enables it to cross the river. Figs. 14.4 and 14.5 show the agent networks created for crossing the highway and the river.

The agent system described above is both holonic and an emergent configuration for the following reasons:

• • The multi-agent networks are created and subsequently destroyed dynamically to achieve a single goal.
• • Each agent is aware of the information it requires to achieve its goal and creates child agents to provide it with that information.
• • Agents lower in the pyramid are not aware of the operation of higher level agents that make use of them (e.g., holonic).
• • Agents dynamically spawn other agents to provide them with the information they need. They are not aware of how the child agents achieve their tasks. They are, in effect, shielded from the complexity of how that information is collected.
• • Interagent communication only occurs between adjacent levels of the pyramid.
• • The complexity of the reasoning capability of agents monotonically decreases as one descends down the layers of the pyramid.

14.5 Reasoning

Reasoning mechanisms enable agents to act autonomously based on the state of the environment, the information available to them, and their inherent abilities. This reasoning has been an active area of research for some time (Stone, 2007 ); the most promising model to date has been the BDI model (Georgeff et al., 1999). In the BDI model agents have a set of beliefs about the world. They also have a set of desires that they plan to achieve. Finally, they have a set of intentions, which consist of the actions they are currently performing to achieve their desires (Stone, 2007). This model is based on a theory of how humans operate. It involves an information-collection stage that forms the agent’s beliefs and a planning stage that generates intents based on the agent’s desires. Planning is a continuous activity that generates a new set of intentions at each time step.

The difficulties with realizing the BDI model is in how each agent state is represented and what reasoning mechanisms are utilized in the planning stage. In the meta-agent approach, agent intents result in the creation of other agents that provide a needed service. This process is true until we reach the leaf nodes where, for the first time, agents are able to interact with IoT devices to collect data.

One can see that as we move along the holonic pyramid, varying levels of sophistication are needed in an agent’s reasoning mechanism. We can expect top-level agents to have a fairly complex reasoning capability, while agents at the bottom of the pyramid have little or no need for reasoning (Gerber, Siekmann, & Vierke, 1999). The challenge then is to utilize a scalable reasoning mechanism that can support these varying levels of complexity.

A behavior tree (BT) (Colledanchise & Ögren, 2018) is a graph-based model of plans of execution that originated in the game industry. They have recently received significant attention in the academic community due to some very desirable properties. First, BTs have a small computational footprint. Second, BTs are able to emulate many other behavior representations including: finite state machines, hierarchical finite state machines, subsumption architectures, teleo-reactive programs, and decision trees. The major advantage of BTs for our use is that they are highly modular, reusable, and hierarchical. The implications for a holonic system is that the reasoning exhibited by the holonic system can be a composition of reasoning modules contained in ach agent comprising the system. Furthermore this configuration supports the idea of scalability in agent reasoning.

14.6 Challenges and Conclusion

Implementing a meta agent–based EC approach for IoT based on the BDI model introduces a number of difficult questions. First, how do agents become aware of the IoT resources available to them? There are currently multiple efforts underway to build open standards for IoT device discovery. Most notable are UPnP and HyperCat. These are relatively low-level standards that generally do not provide a semantic-based service for SOA systems. The need for such a mechanism for IoT has been recognized. It will be some time before universal protocols are developed to provide a universal semantic-based discovery mechanism.

Second, given that the number of IoT devices is estimated to exceed one billion, how do we determine which sources are applicable to our goal without having to inspect over one billion devices? What will be required is a service similar to Google’s web crawlers that crawl IoT spaces and build a database of semantic IoT descriptors that can be quickly searched to establish a set of candidate devices. In fact there is a recently launched effort called IoTCrawler that provides a Google-like search engine for the IoT (Skarmeta et al., 2018). While it will take time for services such as IoTCrawler to mature, it is a promising development towards a generalized semantic capability for IoT devices.