Developing a Symbolic Planner for Automated Action Sequencing

Symbolic Planning: Automated Action Sequencing

The goal of this project was to implement a generic symbolic planner from an environment object, involving parsing descriptions and formulating action sequences in simulated environments.

Problem Setup

The environment was presented as a symbolic description, with my task being to write a planner that inputs this environment object and outputs a sequence of actions. The challenge exemplified by the Blocks world environment included a set of blocks and a table, each with distinct initial and goal conditions defined by their symbolic relationships.

Example Environment

A sample environment I tested my planner on is described as follows:

In this extended environment, the goal is to rearrange colored disks (Red, Blue, Green, and Yellow) on a shelf, with the added complexity of a robotic arm that must first unclip the disks before they can be moved. This environment is designed to simulate a more complex planning scenario that involves additional steps and constraints.

Key Features:

1. Disks: There are four colored disks (Red, Blue, Green, Yellow) that start in a specific stacked arrangement.
2. Shelf: The disks need to be rearranged onto this shelf according to the goal conditions.
3. Robotic Arm: A crucial element that adds complexity. The arm must unclip a disk before it can be moved. Its availability is a factor in the planning process.
4. Clipped/Unclipped State: Each disk begins in a clipped state. The robotic arm must unclip them, transitioning them to an unclipped state, making them eligible for movement.

Initial Conditions: • The disks are stacked in a specific order, with some on the shelf and others on top of each other. • Each disk is initially clipped, preventing immediate movement. • The robotic arm is available for unclipping the disks.

Goal Conditions: • A specified arrangement of the disks on the shelf, different from the initial setup.

Actions: • Unclip: The robotic arm unclips a disk, allowing it to be moved. • MoveToShelf: Move an unclipped disk from its current position directly onto the shelf. • Move: Stack an unclipped disk on top of another disk.

Challenge: The primary challenge in this environment is to strategically plan the sequence of actions, considering both the unclipping and moving of disks, to achieve the desired disk arrangement on the shelf. The planner must manage the constraints imposed by the clipping mechanism and the availability of the robotic arm, making the task more akin to real-world scenarios where multiple conditions must be met before an action is performed.

Planning Approach

1. Completeness: The planner remains complete because it uses the A* search strategy without a depth limit. This means the planner will exhaustively search the entire space until it finds a solution or determines that no solution exists.
2. Optimality: Although the planner uses the A* search algorithm, the optimality of the resulting plan is not guaranteed because the heuristic is inadmissible. An inadmissible heuristic overestimates the distance to the goal, which can cause the A* algorithm to miss shorter paths that it falsely deems less efficient. As a result, the planner may still find a solution, but there’s no guarantee that it will be the best possible one.
3. Domain Independence: The planner is domain-independent, as evidenced by its performance across various scenarios, from stacking blocks to complex tasks like fire extinguishing. This trait is highly beneficial, as it allows the planner to be applied to a wide range of problems without modification. The general search algorithm and the domain-independent heuristic—which is based on state-goal congruence—contribute to its flexibility and adaptability across different domains.
4. Quality of the Plan: The quality of the plan, in terms of the number of steps, may not be the best due to the overestimation by the heuristic. If multiple goal conditions can be satisfied with a single action, the planner might choose a less efficient path because the heuristic suggests that it’s closer to the goal than it actually is.
5. Planning Speed: An inadmissible heuristic often speeds up the search by aggressively focusing on paths that appear to lead more directly to the goal, potentially at the expense of exploring other paths that might offer a more optimal solution. In the context of the provided planner, while the planning speed is high and all problems are solved in well under 60 seconds, this comes with the trade-off of potentially suboptimal plans.

In summary, while the planner is complete and efficient in terms of speed, the use of an inadmissible heuristic means that it can no longer guarantee that the plans it generates are optimal. This trade-off between speed and plan quality is a common consideration in the design of planning algorithms, particularly in complex domains where the computational cost of finding the optimal solution may be prohibitively high

Leveraging regular expressions, the given code parsed the environment descriptions, and my planner used these to plan from the start to the goal conditions. Actions had to be carefully chosen based on the preconditions and effects, reflective of the dynamics of the Blocks world.

For more insight into the planner’s design and its implications, the full report is available here.