1 Introduction
Action selection is a central problem for all intelligent agents: given a set of percepts indicating the state of the world, what actions may the agent select to fulfill its goals? Planning is a powerful technique for action selection, wherein an agent uses an abstract model of the world to plan actions on the world to meet a goal (Blum & Furst, Reference Blum and Furst1997; Nilsson, Reference Nilsson1998; Nilsson, Reference Nilsson2014). To make the problem tractable, many practical planners make simplifying assumptions about the observability of the world and the determinability of the outcomes of actions on the world. These planners work well for short-living agents in highly engineered closed-world environments where the planner can assume complete and correct knowledge of the world (Nilsson, Reference Nilsson1998; Thrun et al., Reference Thrun, Burgard and Fox2005; Nilsson, Reference Nilsson2014). However, these simplifying assumptions tend to break down in (even partially) unstructured, dynamic and open-ended domains. Given that long-living agents in real worlds almost surely will witness changes in their environments, the question becomes how such agents can adapt their knowledge and actions to the changes?
For unstructured, open-ended environments, artificial intelligence (AI) has developed alternative techniques that typically engage plan adaptation or plan learning. In case-based planning, for example, the agent achieves new goals by adapting previously formed plans to achieve similar goals (Leake, Reference Leake1996; Cox et al., Reference Cox, Muñoz-Avila and Bergmann2005; Ontanón et al., Reference Ontanón, Mishra, Sugandh and Ram2010; Hammond, Reference Hammond2012; Riesbeck & Schank, Reference Riesbeck and Schank2013; Kolodner, Reference Kolodner2014). However, case-based planning is typically effective only when the new goals are variations of previously encountered goals. In learning by experimentation, the agent explores the world and uses reinforcement learning (RL) to learn a policy for taking actions in the world (Sutton & Barto, Reference Sutton and Barto1998). Unfortunately, RL can be computationally costly. In learning by demonstration, the agent learns a plan to accomplish a new goal by observing a human teacher (Breazeal & Scassellati Reference Breazeal and Scassellati2002; Breazeal Reference Breazeal2004; Argall et al., Reference Argall, Chernova, Veloso and Browning2009). However, the problem of transfer of the learned model to new situations in an open-ended world remains unsolved.
Recently, there have been several proposals in AI research for integrating some of the above methods, for example, knowledge-based planning and RL. Integrating these methods, the argument goes, may help in combining their advantages, and in using one method to compensate for the limitations of another method. For example, knowledge-based planning may localize and guide RL, thereby reducing the computational cost of the latter (Grounds & Kudenko, Reference Grounds and Kudenko2008; Grzes & Kudenko, Reference Grzes and Kudenko2008; Efthymiadis & Kudenko, Reference Efthymiadis and Kudenko2013); on the other hand, RL might search or analyze the local world and help fill a knowledge gap in the planner (Efthymiadis & Kudenko, Reference Efthymiadis and Kudenko2015; Efthymiadis et al., Reference Efthymiadis, Devlin and Kudenko2016). However, this raises another question: how may we combine the above methods in a principled manner? Existing techniques use the concept of reward shaping (Ng et al., Reference Ng, Harada and Russell1999), meta-reasoning (Murdock & Goel, Reference Murdock and Goel2008), or goal-driven autonomy (Muñoz-Avila et al., Reference Muñoz-Avila, Jaidee, Aha and Carter2010).
In this paper, we describe a multilayered agent architecture that uses meta-reasoning for combining knowledge-based planning and situated learning to learn and adapt solutions to novel situations. In particular, we use hierarchical task networks (HTNs) with modified task representations as for the planning technique and RL as the situated learning method. The planner in our architecture retrieves the most relevant HTN plan from memory and executes it, while the meta-reasoner monitors the execution of the HTN plan, localizes the gap when the plan fails upon execution, invokes the RL method to fill the gap in the HTN knowledge, and thus repairs the HTN plan. While the reason of plan failure can be many, our paper focuses explicitly on changes caused by the addition of new objects with unknown action models to the world.
This work directly builds on our previous work on the Reflective Evolutionary Mind (REM) cognitive architecture for combining meta-reasoning, knowledge-based planning and situated learning (Murdock & Goel, Reference Murdock and Goel2001). The three significant differences are that (1) while REM used Task-Method-Knowledge models arising from work on knowledge systems, our present work uses HTNs that are more common in AI research on planning; (2) while our previous work addressed problems in which the goal of the new task was a variant of the goal of a familiar task, in our present work the new and the known tasks, which we dub original task, have the same goal but different environmental configurations that break planning assumptions; (3) our current paper introduces a more generic and low-level definition for representing and storing plan expectations for discrepancy calculation using occupancy grids.
However, the present work is limited to the addition of objects in the world that render the agent’s world knowledge (correct but) incomplete. Given this condition, the meta-reasoner compares the execution trace of HTN plan for the current task against trace from original task and builds a report describing how do the environmental changes break the object-level assumptions involved. In the current implementation, this means a cell-by-cell comparison of the occupancy grids to note similarities. This report includes the HTN method whose pre-conditions are not met in the current environment, a dissimilarity metric for the extent of mismatch and an array of object-level differences between the two environments. This information is used by the meta-reasoner to create goals and reward heuristics for the reinforcement learner which interacts with the environment of the variant task to learn a new method. Once a new method is learned the meta-reasoner uses the meta-information available to it to plug back the new method with the correct identifiers, or pre-conditions, to fill the gap in the plan from original task. As a result, the learner helps in expanding the method KB of the planner itself.
The remaining paper is organized into an overview of relevant literature followed by sections which go into detail about the methods used and elaborate on our system architecture. We demonstrate this framework for adaptive agents in the micro-world of a Minecraft simulation engine as well as grasp planning for a simulated robot in Gazebo. Our preliminary experiments indicate that the hybrid technique is both faster than pure RL and more flexible than pure HTN in dynamic environments with object additions.
2 Motivating example
In order to understand some of the issues and concepts involved, lets consider an agent called Moon in the world of Minecraft. Moon is a rational agent equipped with a planner and knowledge of the primitive actions allowed in the world. Moon is also a mobile agent, that is, it can maneuver the world and also has a laser-scanner that allows it to ‘see’ the world via laser-scans. A laser-scanner does linear scans of the world at discretized heights and gives back Moon the depth at which it hit an object, and also the reflected value from the object which tell about its material. Our agent lives in a two-room arena with an open door and has the goal of acquiring a gold block placed somewhere in room 2, that is, the room further back in Figure 1 above. Moon also has limited knowledge of the world which consists mainly of the objects it expects to see in the arena and their action models, that is, how do they react to various objects through primitive actions. Moon’s planner also follows a blind planning strategy, that is, it creates a plan assuming each action is going to be successful. When it finds a plan, it shuts down until invoked again for a new plan.
Variant (l) and original (r) Tasks in Minecraft
Moon follows a simple plan that makes it explore the arena until the gold block is sighted, at which point it calls a computationally expensive planner to get a path leading to the gold block. Since Moon has limited resources, it stores the successful plans to re-use. Moon does not want to stray away from the plan, so it also records the state transitions encountered to make sure plan is re-used as expected.
However, Minecraft is a changing world. Imagine there lives a builder who adds new constructions to the world without telling the resident about every small change. The builder decides to build a glass wall in place of the open door without telling Moon or its planner.
This situation is analogous to how we, humans, act in our daily world. We are imprecise and move things around without really announcing every little change. The difference is that for Moon it takes some advanced reasoning to figure out the same change that we humans consider apparent or straightforward to resolve. So now unaware of these changes, Moon starts its task of finding the gold block. However, because of the unexpected glass wall the walking actions of Moon, which lead to room 2, are rendered non-executable. Let’s discuss some of the issues here.
Moon does not have any knowledge of the material glass or how to interact with it. The first question is, how to describe this unknown entity to the planner to plan for? Let’s say somehow Moon decides this an entirely new scenario and it should learn a resolution for this. What should be the learning goal here? Is it possible for Moon to reuse some of the knowledge and prior plan it already has to formulate better goals and make this process more time-efficient? Finally, let’s say Moon does end up learning a policy which leads it to the gold block. How should this policy be represented within its planning framework to re-use in the future? These are a few questions which our algorithm answers in the Approach section.
3 Relevant work
The topic of meta-reasoning has growing literature in AI research. (Cox, Reference Cox2005) and (Anderson & Oates, Reference Anderson and Oates2007) provide useful reviews of some of the literature. (Cox & Raja, Reference Cox and Raja2011) present an anthology of several research projects on meta-reasoning. Our work builds on the Autognostic, REM, Augur, and Game Agent Interactive Adaptation projects (GAIA).
The Autognostic project (Stroulia & Goel, Reference Stroulia and Goel1995; Stroulia & Goel, Reference Stroulia and Goel1999) developed a multilayered agent architecture including situated, deliberative and meta-reasoning components. In analogy to the redesign of physical devices, the Autognostic system viewed an intelligent agent as an abstract device and used a functional model of the agents design to retrospectively repair its deliberative navigational planner. For example, given a failure of the navigation plan, Autognostic used the functional model of the planner to localize the causes of its failure and invoked an adaptation plan from a library (Figures 2–6).
Traditional meta-reasoning architecture
Proposed system architecture: HTN is the planner, RL the learner
Process diagram: an outline of the communication between different processes
Depiction of state-to-occupancy-grid encoding
Original and variant grasping scenario in Gazebo
The REM project (Murdock & Goel, Reference Murdock and Goel2011) built on and generalized the Autognostic agent architecture. It developed a knowledge representation language called task method knowledge language (TMKL) for capturing functional models of agent designs. TMKL is more expressive than HTN; in particular, TMKL sets more explicit expectations about the world states upon completion of tasks, which is useful in localizing the causes of a plan failure. REM addresses both retrospective and proactive adaptations; given a new task such as disassembly of a physical device in proactive adaptation, REM analogically transfers and adapts the reasoning strategy expressed in TMKL for a similar known task such as assembly of the same device. We call this meta-case-based reasoning. Finally, in the retrospective adaption, REM first uses the TMKL model of the assembly planner to localize the causes of a plan failure and then invokes situated RL to learn the repair to the planner.
Unlike the Autognostic and REM projects, the Augur project (Goel & Jones, Reference Goel and Jones2011; Jones & Goel, Reference Jones and Goel2012) focuses on the use of meta-reasoning to diagnose and repair domain knowledge grounded in perception. Given domain knowledge in the form of a classification hierarchy, Augur associates meta-knowledge in the form of empirically verification procedures that capture the expectations about the world states with each node in the hierarchy. When the classifier makes an incorrect prediction, Augur systematically invokes the empirical verification procedures to diagnose the classification knowledge.
Finally, the GAIA project (Goel & Rugaber, Reference Goel and Rugaber2017) provides an interactive CAD-like environment for constructing game-playing agents (for playing Freeciv) in the REM architecture and the TMKL2 language. Given the design of a game-playing agent, GAIA executes the agent in the game environment. If the agent fails, then GAIA enables interactive diagnosis and repair of the agents design.
This present work builds on the above research, and especially the REM architecture and its combination of situated, deliberative and meta-reasoning strategies. However, unlike previous REM research that focused on variations of tasks assigned to an intelligent while keeping the environment constant, this work keeps the task constant but varies the environment through the addition of objects. It complements a similar project on one-shot learning by demonstration in which a robot is given a single demonstration of a task and must transfer what it learned to the same task in a new environment consisting of additional objects (Fitzgerald et al., Reference Fitzgerald, Bullard, Thomaz and Goel2016). In the other project, the robot asks informed questions of the teacher to identify what knowledge to transfer and how to adapt it to the new environment. In the present work, we take the approach of combining planning with situated learning.
Goal-Driven Agents (GDA) (Muñoz-Avila et al., Reference Muñoz-Avila, Jaidee, Aha and Carter2010) is a goal-reasoning framework where the agent makes use of an expectation knowledge base (KB) to keep track of plan execution and find discrepancies if any. GDA is based on meta-reasoning concepts like expectation matching system, discrepancy detection, explanation generation, etc. The central concept of GDA is that goals should have an option to be updated, or reformulated, once plans go awry, based on some reasoning. While (Muñoz-Avila et al., Reference Muñoz-Avila, Jaidee, Aha and Carter2010) follow a rule-based goal formulation scheme, LGDA (Jaidee et al., Reference Jaidee, Muñoz-Avila and Aha2011a; Jaidee et al., Reference Jaidee, Muñoz-Avila and Aha2011b) learns (discrepancy, goal) pairs by experience. (Jaidee et al., Reference Jaidee, Muñoz-Avila and Aha2012) Is perhaps the most advanced GDA formulation where the agent also learns new alternative goals and goal-based policies from experience. GDA generally employs RL as its learning algorithm of choice, which means learning too many alternative goals runs (Jaidee et al., Reference Jaidee, Muñoz-Avila and Aha2012) into the risk of requiring many episodes before becoming competent.
Apart from learning goal formulation, GDA research has also looked at other parts of the pipeline, some of them directly relevant to our current work. Dannenhauer and Muñoz-Avila (Reference Dannenhauer and Muñoz-Avila2015a) use hierarchical plans with annotated expectations, called h-plans, along with a semantic web ontology, to make better assertions about game states and reason at various levels of the plan hierarchy leading to better control over strategy reformulation. Dannenhauer and Muñoz-Avila (Reference Dannenhauer and Muñoz-Avila2015b) look at the problem of creating expectations for a plan and introduces informed expectations which are more general than effects of primitive action but less restrictive than full-state comparisons. Dannenhauer et al. (Reference Dannenhauer, Muñoz-Avila and Cox2016) extend the former to partially observable environments by also considering sensing costs, which is something that our approach also touches on using a low-level variant of expectations, as described in the Algorithm section. Vattam et al. (Reference Vattam, Klenk, Molineaux and Aha2013) provide a survey of research on goal reasoning including goal-driven autonomy.
Another concept proposed by the AI community relevant to our work is of using reward shaping (Ng et al., Reference Ng, Harada and Russell1999) to provide a denser reward to the agent which helps in trimming out unnecessary exploration of irrelevant state-space. Most of the approaches using reward-shaping with a knowledge-based plan (Grounds & Kudenko, Reference Grounds and Kudenko2008; Grzes & Kudenko, Reference Grzes and Kudenko2008; Efthymiadis & Kudenko Reference Efthymiadis and Kudenko2013) to support it come under the umbrella of knowledge-based RL. This relationship also works the other way around where the novel transitions seen during exploration can be used to tag faulty knowledge for revision (Efthymiadis & Kudenko, Reference Efthymiadis and Kudenko2015) or to model a new abstract MDP which reflects the unknown knowledge about the environment (Efthymiadis et al., Reference Efthymiadis, Devlin and Kudenko2016). However, in our paper reward-shaping is not the focus but one of the tools used to incorporate our contribution, that is, a low-level expectation definition, into a RL framework.
4 Background
We are using a modified flavor of HTNs for our planning and plan representation needs, coupled with a hand-coded retrieval system for plan re-use. Simple, tabular Q-learning is being used for learning from experience when the plan breaks down.
4.1 Modified HTNs
HTNs (Erol et al., Reference Erol, Hendler and Nau1994; Nau et al., Reference Nau, Cao, Lotem and Munoz-Avila1999; Nau et al., Reference Nau, Au, Ilghami, Kuter, Murdock, Wu and Yaman2003) are one of the more classic, and more widely used, approaches used in the world of planning. HTNs represent the environment regarding a dictionary of symbolic state variables and task plans. This includes a library of primitive actions and methods. A primitive action is the smallest unit of plan decomposition. A method is a composite action made up of one or more ordered primitive actions or methods. It comprises two primary attributes: pre-conditions and effects. Preconditions are a set of environmental conditions over state variables which must be true for a method to be executed. Effects are the environmental changes triggered by the methods execution. Depending on the goal and the state of the environment HTNs string together these methods to build a complete plan. HTNs are generally non-flexible and not-ideal for dynamic task environments.
To expand the usage of HTNs to meta-reasoning, we have modified the plan representation to also include meta-data from its last successful run, which will be treated as the planners expectation during run-time. This was done so that apart from using case-based retrieval of a plan, the old execution of the plan can also be used to generate insight into the change in environment between variant task and the original task. We describe the nature of this meta-data or expectation in more detail in the Algorithm section below.
4.2 RL: Q-learning
We have implemented a tabular form of learning action Q-values for our RL purposes in this paper (Watkins & Dayan, Reference Watkins and Dayan1992; Sutton & Barto, Reference Sutton and Barto1998). We have used a Q-learning update for our experiments using the following formula. The variable s denotes a state from the table, a denotes the action taken in state s ,
$$s'$$
symbolizes the next state once action a is executed,
$$a'$$
is the action chosen based on Q-values and action-selection policy of the agent while in state
$$s'$$
and
$$R(s,a)$$
is the reward agent received after executing action a while in state s. Q-learning update equation is formulated as follows:
$$Q(s,a){\equals}Q(s,a){\plus}\alpha \cdot \left( {R(s,a){\plus}\gamma \cdot {\vskip11pt arg\ max \atop{{a'}}} Q(s',a'){\minus}Q(s,a)} \right)$$
The rewards in this paper follow a per-action scheme, where each action is given a −1 reward except the terminal state. We chose this scheme so that the agent uses a minimum number of actions to execute the desired behavior. The states of the table vary depending upon whether the q-learner is using domain-knowledge or not, see Section 5 for input state details for both. We have used an ε-greedy selection strategy, with a decaying ε. The decay is controlled by the following formula, where
$$decay\_steps$$
is 100 in our implementation:
$${\varepsilon}\leftarrow{\varepsilon} \cdot decay\_rate^{{{{iteration{__-\!}step} \over {decay{__-\!}steps}}}} $$
5 Approach
5.1 Meta-reasoning: architecture and concepts
Our proposed architecture follows a note-assess-guide strategy (Paisner et al., Reference Paisner, Maynord, Cox and Perlis2013; Cox et al., Reference Cox, Alavi, Dannenhauer, Eyorokon, Muñoz-Avila and Perlis2016). In a few words, this strategy looks for any changes from expected plan execution and makes a note of the event, next it assesses the nature of the discrepancy, and finally uses relevant knowledge to guide a resolution.
In our architecture (Figure 3), object-level layer consists of the sensor-reading, actuator controls (provided by simulation engine and the APIs) and a reactive Q-learner. The deliberative layer houses the planner, its method library and trace memory of plan execution. This trace involves the whole plan annotated with an ordered history of state transitions for every method. These trace memories are the expectations on which our framework bases most of its decisions. The astute reader will note here that we make a strong assumption on the complete and noise-less observability of the environment. Our expectations are the laser-scans that the sensors emit, and we are using 3D occupancy grids (Figure 5) or representing these sensory expectations. The reason for this representation choice is two-fold: (a) occupancy grids are the data structures of choice in robotics community to compress and represent unstructured data, making our approach more readily suitable to such agents; and (b) since we need to describe unknown entities, a representation which accounts for the physical properties made more sense than using any higher-level descriptors. Both the layers described in this paragraph can communicate with each other.
Our final meta-reasoning layer houses the meta-reasoner and has communication channels to and from both the object-level and deliberative layer. This layer is responsible for monitoring to ensure execution matches expectations. If not, we call the event a discrepancy. Concerning the occupancy grid form of expectations, our discrepancy is defined by a dissimilarity score and a list of cell indices where the grid readings do not match.
5.2 Algorithm
Given the birds eye view of our algorithm, lets deep dive into how the components instantiate the note, assess and guide processes. The planning process or phase one starts when the goal is passed to the deliberative layer. If the planner has a stored plan from an original task environment relevant to the current variant task environment, then it is retrieved for execution along with the related expectations sent to meta-reasoner for monitoring. All our agents are equipped with laser scanners which scan a 270-degree area in front of the agent at different heights. Each laser scan tells the agent about the distance of obstacles from itself, and the returned intensity of the laser helps in identifying the material of the obstacle. The state data, originating from these lasers, is communicated to the meta-reasoner at each time-step in the form of occupancy grids. Each cell in the grid has two fields associated with it: a) status: FREE, OCCUPIED or UNKNOWN, and b) reflected reading which tells about the material the laser struck. The height up till which the scans should be considered is specified by the configuration space (Lozano-Perez, Reference Lozano-Perez1983) of the agent, which is a robotics planning concept used to calculate the volume of interest for a plan in which the obstacles are to be avoided. Usually for planning configuration space is created by padding obstacles to find a safe plan, in our case, however, since we already have the path we pad some space around it to represent the physical body of the robot and only look for discrepancies in that volume.
The meta-reasoner compares the execution sensor readings with expectations to catch any discrepancies. Discrepancies are found by calculating a similarity score between the expectation and the sensor reading for each method. If similarity score is lower than a threshold, a discrepancy report is generated which includes the dissimilarity score, a list of grid cell indices which differ and the pre-conditions of all methods in the partial HTN plan after the current method. Our current work uses an extreme threshold of
$$simmax$$
where if the grids are different by even one grid cell, it gets noted. Considering the availability of low-level snapshots of the environment and keeping in mind that the nature of discrepancy is one of the additions of new objects, it is easy to come up with a comparison metric for calculating the similarity between two different instantiations of the same environment. For the current implementation, we use simple addition,
$$sim(x,s')$$
, of a function
$$g(cube_{i}^{x} ,cube_{i}^{{s'}} )$$
over all the cubes of both snapshots. The functions are defined as:
$$g\left( {cube_{i}^{x} ,cube_{i}^{{s'}} } \right){\equals}\left\{ {\matrix{{\!1,\hfill\quad {\rm if}\ x(cube_{i} ){\equals}s(cube_{i} )} \cr {0,\hfill\quad {\rm if}\ x(cube_{i} )\,\ne\,s'(cube_{i} )} \cr } } \right.$$
$$sim(x,s'){\equals}\mathop{\sum}\limits_i g\left( {cube_{i}^{x} ,cube_{i}^{{s'}} } \right)$$
$$sim(x,s')$$
is lower-bounded at 0 and upper-bounded by the product of resolution of the quantization and physical volume of the snapshot area, or
$$simmax$$
. A lower value of this sum indicates a more substantial difference between the two snapshots.
Next is the assess process or phase two, where the meta-reasoner combines the knowledge and experience with RL to learn a discrepancy-resolving policy. For a reinforcement learner to be efficient, it requires achievable goals and guiding reward potential. Our algorithm uses the partial plan after the current method where discrepancy occurred as viable goals to seek since the planner already has methods to achieve the overall goals from those states. Additionally, the meta-reasoner also adds a reward strategy where the agent gets a random cost discount (between 0 and tau<=0.5) for actions which make the environment more like the original task. The intuition for this random reward strategy is that if the agent can manage to make the current environment more like the original, then it should just be able to re-use the plan. Such rewards also encourage interactions with the new entities in the environment indirectly encouraging experimental interactions. These changes are identified by a decrease in the dissimilarity score of the environment. Phase three is the guide process where the reinforcement learner takes the viable goals and rewards and interacts with the environment to learn a discrepancy-resolution policy.
Once the reinforcement learner has learnt a new policy adhering to these goals and rewards (based on some confidence threshold for Q-values or maximum number of interactions), it communicates back to the meta-reasoner alerting it to the availability of a policy for encountered discrepancy and also communicates which of the given viable goals are achieved by this policy. This is the last phase, or phase four of the algorithm, where the meta-reasoner takes the learned policy attaches it to the state where the discrepancy was found as a pre-condition as well as its goal state as an outcome and stores this tuple as a method in HTNs method library for future use.
6 Experimental setup
We use two different simulation engines with a mobile agent and a robotic arm in Minecraft and Gazebo, respectively. The HTN planner (python version of SHOP (Nau et al., Reference Nau, Cao, Lotem and Munoz-Avila1999) called PyHop) assumes a separate controller is used for low-level joint movements and only plans for more abstract task primitives. Both the agents use the same meta-reasoning framework but have different task specifications and original-variant environment settings. We have kept the problems relatively simple in our experiments since we wanted to focus on verifying our concept first rather than evaluating the robustness of the system. We present a quick summary of the experiments here to make the details clear to the reader.
6.1 Gold-hunting in Minecraft
This experiment follows directly from our motivating example. The agent lives in a two-room arena and is tasked with finding a gold block in the second room (Figure 11). For original-variant modification, the arenas open door is replaced with a glass wall. We have used the Malmo project for integrating Minecraft environment with rewards for RL. The primitive actions in this experiment are: ‘move forward’, ‘turn left/right’, ‘look up/down by 45 degrees’ and ‘break the block in focus’. The input state for pure reinforcement learner consisted of the 3(height)3(width) blocks right in front of the agent including: the ground blocks, what the agent is staring at, what is the agent holding in its hand and agent’s pitch state, that is, the angle at which the agent is staring. The terminating conditions of this experiment were either acquiring the gold and a reward or breaking the walls or ground of the room in which case the agent was considered to have failed. After some calibration, our implementation uses a starter ε of 0.4 with a decay rate of 0.95 over 1000 iterations, a learning rate, α, of 0.55 and a γ of 0.75. In addition, the Q-values were normalized to sum to 50.
6.2 Grasping a can of coke
Our second experiment is using the Gazebo simulator (Koenig & Howard, Reference Koenig and Howard2004) along with a robotic arm whose goal is to pick up a can of coke placed on the table-top. We have used Gazebo’s API for the reward and environment management, and a Q-learner for RL purposes. The primitive actions here are: ‘pick a specified object’ and ‘place object in hand on the table at
$$\left( {x,y} \right)$$
’.
The HTN planner plans a path for picking up the can of coke in an original environment which is free of litter, while in the variant task the configuration space of the path is obstructed by solid cubes. The plan for this experiment is more low-level as compared to the gold-hunting scenario. It consists of an ordered list of three-dimensional points the arm’s gripper should follow before it closes to grasp the can. Therefore, the intermediate goals here are clearing out individual segments of this plan, of the obstacles, for the gripper to move through. Since the arm is an immobile and fixed agent, the only way to get around the clutter is to interact with it using our meta-reasoner.
It is to be noted in this setup that both primitive actions are dependent on two other random variables, that is, the choice of object,
$$O_{i} $$
, and placing position of the object in hand on the table,
$$\left( {x_{{O_{i} }} ,y_{{O_{i} }} } \right)$$
respectively. Moreover, these two actions are also mutually exclusive, the arm cannot pick up another object before placing the object in hand somewhere, and an object cannot be placed if the gripper is empty. Therefore, the actual complexity lies in knowing which object to manipulate and at what position to place the object. Consecutively the learning in this experiment takes place for these two random variables as opposed to a. The input to reinforcement learner is given as a
$$\left( {n{\plus}2} \right)$$
-tuple, where n is the total number of new objects in the scene. This consists of an n-tuple hot vector,
$$\hat{o}{\equals}\{ o_{1} ,o_{2} ,\,\ldots\,,o_{{n{\minus}1}} \} $$
,where
$$o_{i} $$
is 1 if object
$$O_{i} $$
lies in collision with the padded path plan suggested by the original task plan. This hot vector is appended with two more categorical variables signifying the state of the robot namely, state of agent’s gripper (open/close) and reference to object in the agent’s hand. The configuration space of the planned path is thresholded at 1 foot or 0.3 meters around the path plan to account for control errors in robotic execution and compensate for the size of the gripper. The hyper-parameters used for this experiment:
∙ a starter ε of 1.0 with a
$$decay\_rate$$
of 0.95 over 3000 iterations,∙ a decaying learning rate starting at 1.0 following same decay as ε,
∙ and a greedy, decaying γ starting at 0.1 with a
$$decay\_rate$$
of 0.93.
The table-top positions, in an ideal world, will be conditioned on the attributes of the object being placed. However, in our experiment all the novel objects are identical, that is, cubes. Therefore, we have learned these positions as a Gaussian Mixture Model (GMM) of the placements which lead to the emission of a positive reward. Position selection also follows the same strategy of epsilon-greedy as the object selection, that is, either choose a position on table randomly with a probability of ε or randomly select from the rewarding poses stored in the GMM. The state representation being used for RL affects the learning curve. Therefore, for the fairness of comparison, we have supplied the same reduced state to the pure learner as well as are using the same hierarchical learning setup, with the difference being that the combination learner receives the intermediate rewards for making the variant environment more like the original.
7 Experimental results
We evaluate our results on two different aspects: the ability to completely solve the novel variant task, and its time efficiency as compared to a vanilla learner. The former is simply a score of whether the agent can reach the goal state or not. It is a binary score of 0 or 1.
The latter metric is to compare the efficiency of our proposed architecture versus one which cannot reason about the failure of a plan and decides to employ an end-to-end learner which learns a complete plan from breakage point to the final goal. For this, we create a new pipeline and run it on the variant configuration. Instead of reasoning about information gap and learning a bridging method, this pipeline follows a vanilla epsilon-greedy learning policy by employing a learner which learns an entirely new method from the point of failure with its goal as gold block acquisition. We then compare the training time and resultant accuracy between this brute end-to-end learner pipeline with our results from our architecture.
7.1 Gold-hunting scenario
Figure 7 shows the comparison between end-to-end learner and our combination learner for the two different method learning scenarios. We would like to point out an interesting observation here when combination learner is compared against the pure RL agent, the latter resulted in zero percentage of success in completing the mission over 1000 iterations. We hypothesize that the proposed scenario was a little too complicated for a simple algorithm like zero-order tabular Q-learning to formulate. The solution required three different actions strung in a row together without missing a beat, which was hard for a no memory technique to make tractable. Therefore, the results that we show are contrasting between vanilla RL with viable goals available and combination learner with viable goals as well as action cost discounts available.
Comparing action Q-values for different approaches in Minecraft environment
As readers can see in Figure 7, the Q-values for pure RL approach first takes a dip before gaining value. This is due to the agents repeatedly wrong actions which further decrease its confidence. The topmost plot shows a considerable number of spikes and jumping around for the Q-values, this is because the ε for our action-selection strategy is still high with the lowest value of 0.25. This leads to execution of random actions by the agent, but since our environments solution relying on a strictly sequential series of actions even one wrong random action can lead the agent down an action trajectory with zero reward returns. The most important results can be seen in the second subplot in the figure, where our combination learner performs significantly better than the pure reinforcement learner. We have used an averaged plot of Q-values here to account for randomness introduced by moderately high value and to display the comparison more clearly.
7.2 Grasping scenario
Figure 8 shows the comparative results over various aspects of the pure learner and combination learner. These results are solely for learning which objects to be picked up to clear the plan area and use a rolling mean on a window of 50 episodes to display a clearer picture. Not only does the combination learner stay ahead of the pure learner, but it does so by a margin of 750 episodes, regarding succeeding consistently (sub-figure 8(d)). Moreover, as can be seen in sub-figure 8(c), the combination learner can learn the most efficient way of solving this problem with a minimum number of moves which the pure learner does not approach even after 3000 episodes. The biggest reason for this difference is related to sub-figure 8(b). The combination learner starts off with a comparatively confident estimate of Q-values which helps in shaping its exploration later by pushing it towards the more ‘fruitful’ state-space. Figure 9 shows the learned heat-map for good placements of the picked object on the table such that the ‘plan area’ remains cleared.
Comparison of pure-learner with combination-learner for Gazebo task
Learned distribution of good table-top placement locations (x marks the location of the can)
8 Discussion
We would like to begin by discussing some of the assumptions and limitations of our method. Our procedure makes strong assumptions about complete and noiseless observability, as well as the class of problems it is tackling. We still need to conduct some exploratory work to see how much of our framework can be applied to environments which change differently. Furthermore, basing discrepancies on a pixel-by-pixel or cell-by-cell comparison can be extreme for noisy sensors. It would be better if we can learn or reason for a baseline about how much dissimilarity is harmless.
Matrix computations are already costly, and when scaled up to a whole environment this comparison can be hard to handle for a resource-limited platform. Resource exhaustion is an issue that our usage of occupancy grids had the potential to run into, but the use of configuration spaces to prune down the sensor information to a much smaller volume and using grids to compress the data by discretization further helped immensely. Not only was this effect evident in computation time, but also concerning the learning curve since the state data was now based on a much smaller set of environment cells, which affects tabular Q-learning.
One of the critical insights about our algorithm stems from Figure 9, that is, our approach does not improve much for problems where the goal is to learn the distribution of the value of a random variable. However, our approach evidentially holds merit for problems seeking a chain of actions as the solution, Figure 7 and Figure 8. Another interesting observation is illustrated in Figure 10 where our agent learns ‘how to not die’ faster than the naive learner. Such an ability is essential for environments where the reward is delayed, and it is imperative for the agent to be active until then.
Number of moves taken by Minecraft agent per episode
Lastly, we want to compare our method against some of the contemporary work. (Dannenhauer & Muñoz-Avila, Reference Dannenhauer and Muñoz-Avila2015a) prove that hierarchical expectations work better than flat plans and expectations for reasoning about goals; however, their semantic ontology of expectations are much more restrictive than our occupancy grids. Comparing our work to the KBRL spectrum, there are similar themes like reward shaping using a known plan (Grounds & Kudenko, Reference Grounds and Kudenko2008; Grzes & Kudenko, Reference Grzes and Kudenko2008), however, in our case, we dealt with a particular class of problems where apart from original plan the knowledge of how the environment has changed also affected the reward function. (Efthymiadis et al., Reference Efthymiadis, Devlin and Kudenko2016) look at a problem where stored, possibly incorrect, knowledge is revised for a specific task but they use a propositional form of expectations, and in contrast to their assumption of wrong information our system assumes known information is correct and focuses on learning new knowledge for overcoming the seen discrepancy. Additionally, our results reflect the findings of (Ulam et al., Reference Ulam, Goel, Jones and Murdock2005; Ulam et al., Reference Ulam, Jones and Goel2008) where they saw a considerable speed-up of the learning process by providing it with internal model and knowledge about the game world. However, our algorithm does not rely on as strict a definition of expectations and outlines a more general method of representing and calculating similarities at a lower-level, applicable to any map-based world.
9 Conclusion
This paper presented a meta-reasoning architecture and approach for building AI agents situated in dynamic environments in which new objects with unknown action models are added. The architecture combines HTN planning and Q-learning within the meta-reasoning architecture. We performed experiments on two different tasks on two different platforms to test and evaluate our architecture. Our results suggest that the meta-reasoner can use the Q-leaner to complete the plans for the HTN planner in the new environment with added objects. This capability is potentially valuable because it enables us to have a flexible planner capable of extending its KB to new worlds.
Moreover, we used low-level percepts in the form of occupancy grids for comparing plan expectations and actual observations, which makes our work suitable not only for software agents in simulated environments but potentially also for embodied agents that work on real raw data. Additionally, we showed that the guidance that the HTN provides to reinforcement learner helps in scoping the exploration of a large state-space by a significant factor. Such an architecture beats pure data-driven learners not only concerning learning efficiency but also flexibility since learned methods are grounded in states and can be strung together in any order to accomplish different tasks.
Appendix A Algorithms
Central planning and execution algorithm
Meta-reasoner algorithm
