Automated Planning and the Associated complexities
Solution
An agent (human or artificial) attempting to achieve its goals in the world must often reason about two things: (1) the actions or steps that should be taken, and(2the order in which these steps should be performed. The process of identifying the necessary steps and andt heir appropriate order is called “planning” and it is at ask that humans perform all the time (e.g., taking a trip, cooking a meal, communicating with other agents, etc.).
Automated planning is an artificial intelligence research area that attempts to understand the planning process computationally and to build tools for solving planning problems. In particular, automated planning techniques are good at building goal-directed plans of action under many challenging conditions, given a suitable description of the domain.
A planning problem usually consists of 4 parts:
1) A model of the properties and objects in the world, usually described in a logical language,
2) A model of the actions the agent can perform,
3) A model of the initial state, and
4) A set of goal conditions to be achieved.
A plan is then a sequence of actions that when applied to the initial state, transforms the state in such a way that the resulting state satisfies the goal conditions.
Modern planning research has introduced languages like PDDL (the Planning Domain
Definition Language) for representing planning problems, and built different types of planning engines that can solve planning problems (e.g., the cloud-based planner at
http://planning.domains). PDDL provides a standard representation of planning problems allowing different types of planning engines to be used to solve the same problem. Some planning engines (also called “planners”) might be better at solving some problems than others (i.e., provide betters plans, be quicker), while some planners might not be able to solve the problem at all. In some cases, it’s possible that no planner could solve certain types of planning problems because they’re too difficult. In that case, researchers attempt to build better planning algorithms and better tools; however, this is a difficult task.
Automated planning has been around since at least the 1960s and has been applied to a number of tasks. One of the popular areas for automated planning applications has been robotics, i.e., use planning to direct a robot to achieve certain goals in the world. One area that has been of recent interest is the idea of using planning for interaction (communicating with other agents) and collaboration (helping another agent perform a task). However, more research is needed to understand when planning can be used and how well it performs in certain types of interactive and collaborative domains.
PROJECT QUESTIONS
The “goal reasoning” paper by Geib, Craenen, and Petrick describes a simple framework for identifying situations where an agent can build collaborative plans: plans to help another agent achieve its goals. The paper also focused on a “table setting” situation as an example of an everyday situation where one agent might help another agent. However, there are still many research questions that need to be answered within this approach. Some of these questions can form the basis of your Master’s project.
2) How large can the table setting examples in the goal reasoning paper get before they become difficult for planning? In other words, if we continue to add more objects to the problems, is it still solvable? Compare with a set of planners.
Write a draft of Research Report.
Solution
Automated Planning and the Associated complexities
Introduction
Planning is described as the process of organizing sets of tasks that are aimed at achieving a set goal. The states needed to complete a specific task depends on the complexity of the domain of the problem – a complex domain contains more states than a simple domain. For planning to be successful, the initial state and the goal state have to be known. In between the initial state and the goal state there are some steps or actions that have to be performed. In short, planning constitutes the initial state, goal state and sets of actions that must be performed to reach the goal state from the initial state. Automation is the application of technology in systems to make them function automatically without or with minimal human intervention (Mills, 2005). Automated planning (AP) can therefore be described as a branch of AI (Artificial Intelligence) that aims at computationally exploring planning process. AP was introduced in late 1950’s to assist in automatic deduction and robotics. Since then, AP studies are broadening in scope from toy applications to real world applications. However, applying AP in real world problems is not a simple task.
The complexities associated with automated planning are mainly related to the quality of solutions produced and the time taken. For instance, off the shelf planners rarely produce quality solutions. There are two main categories of planning – temporal and metric. In temporal planning time is of much essence than the sequence or number of actions performed to attain the goal state. Timing problems may arise due to stringent deadlines, uncontrollable actions that consume a lot of time or shortage of resources. Metric or numeric planning is concerned about resource availability as well as the number of resources available. Real world problems associated with both metric and temporal planning are normally very complex to solve.
Automated planning aims at producing planners than solve different types of problems from different environments. An Automated Planning task is defined by the domain and the problem. The domain is the set of states and actions in the environment while the problem is consist of the facts about the initial state and the goal state (Rosa et al. 2009). The solution to the task consists of the set of actions corresponding to the states in the domain that are followed to reach the goal state from the initial state. Various researchers have come up with planners that can be used in solving automated planning tasks. For instance, Geib et al (2016) present a framework that integrates recognition, planning and goal reasoning in creating collaborative agents. They make use of two agents, the initiator and supporter, to demonstrate the framework. In this case, the supporter, which is assumed to be an artificial agent, is supposed to help the initiator agent to achieve its goals. The initiator agent can be either human or artificial. In plan recognition, the sub goals, both accomplished and anticipated, are identified. Goal reasoning assists in identifying and understanding the main goal of the initiator. Through this, the supporter is able to identify sub goals that help in achieving the main goal. Lastly, planning helps in identifying the actions to be performed in order to attain the main goal and sub goals. They use the two agents and a table setting example to test the framework. Though it proved to work well, the problem would prove to be more complex if more activities are to be added to the table example.
Foster and Petrick (2013) also describe how automated planning can be applied in social-interaction between robots and several human agents. In their case, they make use of a task based bartending robot that interacts with several customers. In Artificial Intelligence (AI), an agent can be described as an entity that perceives the environment through sensors and then acts upon it through actuators. A robot is an intelligent agent that is intended to perceive its environment and act upon it (Rudowsky, 2004). In the case of bartending robot, information is collected from environment through sensors in form of speech and vision. A PKS planner is used to construct plans depending on the task at hand, social actions and dialogue. The robot has to constantly read the social behavior of the people entering the bar and be able to sustain a dialogue and synthesize speech in order to perform adequately. As each customer enters the bar area, the robot attends to them appropriately. The vision system ensures that it tracks the position and body posture of a customer, the speech recognition system ensures that it keeps track of the speech of a customer in order to get what the requires and the reasoning system evaluates the desires of a customer and ensures that he or she gets required services. To ensure that all customers are served appropriately and in the order in which they came in, the system has to react to each customer that comes in. Though their bartending robot project proved successful, it may have some short comings. For instance, in case many customers come in at a time, then the vision sensor may not collect the appropriate data. Collection of inappropriate data may affect planning process. Such mistakes may in turn increase or lead to timing problems. With such complexities, one tends to question the viability or practicability of planners in intelligent agents. This report therefore seeks to describe planners and unravel the complexities or problems that are associated with automated planning applied in robots. The remaining portion of the report discusses search algorithms, planning algorithms, planning languages and lastly planners together with their associated problems.
Search Algorithms
As stated earlier, Automated Planning makes use of a sequence of actions to move from the initial state to the goal state. In order to get the appropriate sequence of steps required to reach the goal state, an agent makes use of a specific search algorithm. Though a goal state can be reached using various paths, an appropriate path that fulfils time constraints has to be chosen. A good search algorithm should avoid paths that will consume a lot of time in reaching the goal state. A planner should give the most appropriate solution to planning problems. A planner that involves many states also requires a lot of space to store the different states. Search algorithms are very important as they assist in finding the most appropriate states to be used by planners. Search algorithms are divided into two main categories – informed and uninformed search. Informed search comprises Best First Search (BFS), Greedy Best First Search (GBFS), A* Search etc. while uninformed search comprises Breadth First Search (BFS), Depth First Search (DFS) etc.
- Best First Search (BFS): This algorithm uses heuristic function to identify a node that can be explored depending on its cost to the goal.
- Greedy Best First Search (GBFS): This a special case of BFS whereby the node explored is the one assumed to be the nearest to the goal.
- A* Search: This algorithm is also a special case of BFS that makes use of both path costs and approximate cost to the goal state to ensure that an optimal solution is found.
- Breadth First Search (BFS): This is a complete algorithm that explores all the nodes in a level in order to reach a goal state.
- Depth First Search (DFS): This algorithm explores all the nodes in a branch before moving to another branch in a tree.
Planning Languages
This are languages that describe the initial state, the sequence of actions, and the goal state that an agent is supposed to use in planning problems. They include STRIPS (Stanford Research Institute Problem Solver), ADL (Action Description Language), PDDL (Planning Domain Definition Language) etc.
STRIPS: It is a language used in classical planning that defines planning problem using a set of states. It makes use of A* search algorithm to determine the most appropriate node to be explored from the current state in order to reach the goal state. It was initially created for a robot that was used to move objects from one place to the other.
ADL: This language is simply an upgrade of STRIPS. It functions by identifying a condition that yields a set of actions that can help reach the goal state. Each action has some preconditions for it to take place and when it takes place, it causes some changes in the environment.
PDDL: It is used in classical planning. PDDL is used in representing temporal planning problems. It consists of initial state, goal state, objects and their attributes and the actions required to achieve the goal. However, it is rarely used because most of the planners cannot support PDDL.
Planning Algorithms
Planning is categorized into two – classical and non-classical. In classical planning, planners have all the required information about initial states. Classical planning takes place in environments that are static, finite and deterministic. In non-classical planning, a planner does not have all the information about the initial state. For this reason, the actions and the time to be taken is not known. Planning algorithms include forward search algorithm, backward search algorithm, partial order planning algorithm etc.
Forward search algorithm: In this algorithm, the planner receives the problem description as input. It then starts from the initial state and explores other states using various actions to reach the goal. Though this algorithm requires a lot of space, it is optimal.
Backward search algorithm: This algorithm tries to find the most appropriate path for solving a problem by starting with the goal state. The goal state is then expounded to find the sub goals that lead to the main goal state. The expansion continues until the initial state is reached.
Partial order planning algorithm: This algorithm employs the divide and conquer technique. It divides the problem into sub problems then each sub problem has its own sub goals and sub plans that are solved separately. The results are then combined to produce the final solution.
Complexities in Planners
Planners are automated problem solving systems that are aimed at finding solutions to many planning problems. A planners output is the instruction that helps in reaching a specific destination. It is like an algorithm or program that takes in problem description then gives a plan as its output. Planners are mostly used in robots to assist in achieving specific goals. For a planner to function properly, the initial state, goal state, and the sets of actions to be performed to achieve the goal must be known. As stated earlier, a planner takes in the problem domain and gives out a plan. A plan is simply a sequence of instructions that should be followed by an agent to perform a specific task. Some agents, created to support other agents in accomplishing tasks, have to create sub plans that will be used in helping the main agents. Such supportive agents have to ensure that the main goal of the main agent is achieved by helping in achieving its sub goals. In cases where more than one agent is used in planning, collaboration is required. The collaboration ensures proper communication between the main agent and the supportive agent in order to come up with appropriate plan.
Geib et al (2016) demonstrated how multi agent planning can be performed through their framework. They used two agents in a “setting table” example to demonstrate their idea. They had three scenarios in which the supportive agent interacted with the main agent in order to understand the main goal. From understanding the main goal, the supportive agent deduces the sub goals to be achieved. After identifying the sub goals, a plan is created that helps in achieving the sub goals. Though their idea proved successful, increasing activities in the table example will make the problem more complex. For instance, if the initiator agent had three main goals – set-table, wash-plates, and wipe-plates – which may also be used as sub goals, then planning may be difficult for the supportive agent. Let’s assume wash-plates is the immediate sub goal of wipe-plates and wipe-plates is an immediate sub goal of set-table, such that before plates are placed-on-table they have to be wiped and after plates are washed they are wiped. Since not every time plates are wiped a table is being set, a supportive agent may end up setting a table in cases where plates are being washed, wiped and stored. This complexity may make planning difficult to achieve.
Foster and Petrick (2013) also created a bartender robot that interacts with customers as described earlier. Though it proved to work properly, miscommunication between the bartender robot and the customers would make planning difficult. For instance, if the visual system picks the wrong information then planning would be difficult to accomplish. In cases where customers are too many and the agent has to pick the position and posture of a customer, it is bound to pick the wrong information through its vision sensor. Responding to all those customers to wait may also drag the process. Dragging of the process can be attributed to poor or delayed planning. Foster and Petrick and Geib et al show that the main complexity associated with automated planning is time. The more complex the actions to be performed become, the more difficult the planning process.
Apart from planners that solve classical problems, there are temporal planners that make use of durative actions. They are usually dedicated to a single agent. An example of a temporal planner is SAPA that makes use of forward chaining A* search algorithm to solve planning problems. SAPA is a good planner because it finds better solutions and ensures the quality of the solution. There is also HSP (Heuristic Search Planner) that uses heuristic function to solve problems. This planner uses either informed or uninformed search algorithm. The main problem with this planner is that if it uses A* search algorithm then it is bound to take long to reach the goal state. This shows that temporal planners are also faced with time problems. A temporal planner has to keep track of both the order of tasks and the time taken by each task. This is because time is a great influencer of the performance of planners.
Conclusion
Automated planning is a branch of AI that is used in computationally
exploring planning process. It is mainly applied in robots to help in
accomplishing specific tasks. For a successful automated planning, the initial
state, goal state and the sets of actions to be performed to achieve the goal
state have to be known. This is referred to as the problem description. A
planner takes in a problem description then gives a plan as the output. Algorithms
used in automated planning include forward search algorithm, backward search
algorithm, and partial order planning algorithm among others. Though several
studies show that automated planning can be applied in both single and
multi-agent environments, its practicability is still unconvincing. This is
because complex domains still pose some level of problems to planners. The more
complex a domain is the more complex the planning process becomes.
References
Petrick, P., A., R., & Foster, M., E. (2103). Planning for Social Interaction in a Robot Bartender Domain. Association for the Advancement of Artificial Intelligence.
Geib, C., Craenen, B., & Petrick, P., A., R. (2016). Combining Plan Recognition, Goal Reasoning, and Planning for Cooperative Task Behavior.
Rudowsky, I. (2004). Intelligent Agents, Proceedings of the Americas Conference on Information Systems, New York, 2014.
Mills, F., & Stufflebeam, R. (2005). Introduction to Intelligent Agents. Retrieved from http://www.mind.ilstu.edu/curriculum/ants_nasa/intelligent_agents.php
Rosa, T., L., Jimenez, S., Fernandez, S., Fernandez, F., & Borrajo, D. (2009). A Review of Machine Learning for Automated Planning. The Knowledge Engineering Review, 0(0): 1–24