Task Planning in robotics – Robohub

Suppose now we have a robotic in a easy world just like the one under. Let’s take into account commanding our robotic to carry out a process akin to “take the apple from the shelf and put it on the table”.

Simple process planning instance world: A robotic can transfer between a finite set of places, and may choose and place objects at these places.

I might argue we people have fairly good instinct for the way a robotic may obtain this process. We may describe what the robotic ought to do by breaking the answer down into particular person actions. For instance:

• Move to the shelf
• Pick up the apple
• Move again to the desk
• Place the apple

This is okay for our easy instance — and in reality, can also be effective for a lot of real-world robotics functions — however what if the duty will get extra sophisticated? Suppose we add extra objects and places to our easy world, and begin describing more and more advanced objectives like “make sure all the apples are on the table and everything else is in the garbage bin”? Furthermore, what if we wish to obtain this in some optimum method like minimizing time, or variety of whole actions? Our reasoning shortly hits its restrict as the issue grows, and maybe we wish to take into account letting a pc do the work.

This is what we regularly consult with as process planning: Autonomously reasoning in regards to the state of the world utilizing an inside mannequin and arising a sequence of actions, or a plan, to attain a objective.

In my opinion, process planning isn’t as widespread as different areas in robotics you may encounter as a result of… fairly frankly, we’re simply not that good at robotics but! What I imply is that robots are sophisticated, and lots of commercially obtainable programs are automating easy, repetitive duties that don’t require this stage of high-level planning — it will be overkill! There are many lower-level issues to unravel in robotics akin to standing up good {hardware}, sturdy sensing and actuation, movement planning, and protecting prices down. While process planning skews in the direction of extra tutorial settings because of this, I eagerly await the not-so-distant future the place robots are much more succesful and the whole business is considering extra about planning over longer horizons and more and more subtle duties.

In this put up, I’ll introduce the fundamental items behind process planning for robotics. I’ll give attention to Planning Domain Definition Language (PDDL) and take you thru some fundamental examples each conceptually and utilizing the pyrobosim instrument.

Defining a planning area

Task planning requires a mannequin of the world and the way an autonomous agent can work together with the world. This is often described utilizing state and actions. Given a specific state of the world, our robotic can take some motion to transition to a different state.

Over the years, there have been a number of languages used to outline domains for process planning. The first process planning language was the STanford Research Institute Problem Solver (STRIPS) in 1971, made widespread by the Shakey undertaking.

Since then, a number of associated languages for planning have come up, however one of the vital widespread right now is Planning Domain Definition Language (PDDL). The first PDDL paper was printed in 1998, although there have been a number of enhancements and variations tacked on through the years. To briefly describe PDDL, it’s arduous to beat the unique paper.

“PDDL is intended to express the “physics” of a website, that’s, what predicates there are, what actions are attainable, what the construction of compound actions is, and what the consequences of actions are.”

– GHALLAB ET AL. (1998), PDDL – THE PLANNING DOMAIN DEFINITION LANGUAGE

The level of languages like PDDL is that they’ll describe a whole area of attainable issues the place a robotic can take the identical actions, however in numerous environments and with completely different objectives. As such, the basic items of process planning with PDDL are a task-agnostic area and a task-specific downside.

Using our robotic instance, we will outline:

• Domain: The task-agnostic half
  • Predicates: (Robot ?r), (Object ?o), (Location ?loc), (At ?r ?loc), (Holding ?r ?o), and so on.
  • Actions: transfer(?r ?loc1 ?loc2), choose(?r ?o ?loc), place(?r ?o ?loc)
• Problem: The task-specific half
  • Objects: (Robot robotic), (Location shelf), (Location desk), (Object apple)
  • Initial state: (HandEmpty robotic), (At robotic desk), (At apple shelf)
  • Goal specification: (At apple desk)

Since domains describe how the world works, predicates and actions have related parameters, that are denoted by ?, whereas a particular object doesn’t have any particular characters to explain it. Some examples to make this concrete:

• (Location ?loc) is a unary predicate, which means it has one parameter. In our instance, shelf and desk are particular location cases, so we are saying that (Location desk) and (Location shelf) are a part of our preliminary state and don’t change over time.
• (At ?r ?loc) is a binary predicate, which means it has two parameters. In our instance, the robotic could start on the desk, so we are saying that (At robotic desk) is a part of our preliminary state, although it might be negated because the robotic strikes to a different location.

PDDL is an motion language, which means that the majority of a website is outlined as actions (typically known as operators) that work together with our predicates above. Specifically, an motion incorporates:

• Parameters: Allow the identical kind of motion to be executed for various combos of objects which will exist in our world.
• Preconditions: Predicates which have to be true at a given state to permit taking the motion from that state.
• Effects: Changes in state that happen because of executing the motion.

For our robotic, we may outline a transfer motion as follows:

(:motion transfer
:parameters (?r ?loc1 ?loc2)
:precondition (and (Robot ?r)
(Location ?loc1)
(Location ?loc2)
(At ?r ?loc1))
:impact (and (At ?r ?loc2)
(not (At ?r ?loc1)))
)

In our description of transfer, now we have

• Three parameters ?r ?loc1, and ?loc2.
• Unary predicates within the preconditions that slim down the area of parameters that make an motion possible — ?r have to be a robotic and ?loc1 and ?loc2 have to be places, in any other case the motion doesn’t make sense.
• Another precondition that’s state-dependent: (At ?r ?loc1). This implies that to carry out a transfer motion beginning at some location ?loc1, the robotic should already be in that location.

Note that in some circumstances, PDDL descriptions permit for typing, which helps you to outline the area of actions inline with the parameters reasonably than explicitly together with them as unary predicates — for instance, :parameters ?r – Robot ?loc1 – Location ?loc2 – Location … however that is simply syntactic sugar.

Similarly, the consequences of the motion can add new predicates or negate present ones (in STRIPS these have been specified as separate addition and deletion lists). In our instance, after performing a transfer motion, the robotic is not at its earlier location ?loc1 and as an alternative is at its meant new location ?loc2.

An identical idea may be utilized to different actions, for instance choose and place. If you are taking a while to course of the PDDL snippets under, you’ll hopefully get the gist that our robotic can manipulate an object solely whether it is on the identical location as that object, and it’s presently not holding one thing else.

(:motion choose
:parameters (?r ?o ?loc)
:precondition (and (Robot ?r)
(Obj ?o)
(Location ?loc)
(HandEmpty ?r)
(At ?r ?loc)
(At ?o ?loc))
:impact (and (Holding ?r ?o)
(not (HandEmpty ?r))
(not (At ?o ?loc)))
)

(:motion place
:parameters (?r ?o ?loc)
:precondition (and (Robot ?r)
(Obj ?o)
(Location ?loc)
(At ?r ?loc)
(not (HandEmpty ?r))
(Holding ?r ?o))
:impact (and (HandEmpty ?r)
(At ?o ?loc)
(not (Holding ?r ?o)))
)

So given a PDDL area, we will now come up a plan, or sequence of actions, to unravel varied kinds of issues inside that area … however how is that this performed in follow?

Task planning is search

There is nice motive for all this overhead in defining a planning area and language to precise it in: At the top of the day, process planning is solved utilizing search algorithms, and far of the literature is about fixing advanced issues as effectively as attainable. As process planning issues scale up, computational prices improve at an alarming charge — you’ll typically see PSPACE-Complete and NP-Complete thrown round within the literature, which ought to make planning folks run for the hills.

State-space search

One technique to implement process planning is utilizing our mannequin to carry out state-space search. Given our downside assertion, this might both be:

• Forward search: Start with the preliminary state and broaden a graph till a objective state is reached.
• Backward search: Start with the objective state(s) and work backwards till the preliminary state is reached.

Using our instance, let’s see how ahead state-space search would work given the objective specification (At apple desk):

(1/6) In our easy world, the robotic begins on the desk. The solely legitimate motion from right here is to maneuver to the shelf.

(2/6) After shifting to the shelf, the robotic may both choose the apple or transfer again to the desk. Since shifting again to the desk leads us to a state now we have already seen, we will ignore it.

(3/6) After selecting the apple, we may transfer again to the desk or place the apple again on the shelf. Again, inserting the apple would lead us to an already visited state.

(4/6) Once the robotic is on the desk whereas holding the apple, we will place the apple on the desk or transfer again to the shelf.

(5/6) At this level, if we place the apple on the desk we attain a objective state! The sequence of actions resulting in the state is our ensuing plan.

(6/6) As the variety of variables will increase, the search downside (and time to discover a answer) grows exponentially.

Deciding which states to broaden throughout search may very well be purely primarily based on a predetermined traversal technique, utilizing normal approaches like breadth-first search (BFS), depth-first search (DFS), and the like. Whether we resolve so as to add prices to actions or deal with all of them as unit value (that’s, an optimum plan merely minimizes the entire variety of actions), we may as an alternative resolve to make use of grasping or hill-climbing algorithms to broaden the subsequent state primarily based on minimal value. And lastly, no matter which algorithm we use, we in all probability wish to maintain observe of states now we have already beforehand visited and prune our search graph to stop infinite cycles and increasing pointless actions.

In movement planning, we regularly use heuristics throughout search; one widespread instance is the usage of A* with the straight-line distance to a objective as an admissible heuristic. But what is heuristic within the context of process planning? How would you outline the gap to a objective state and not using a helpful metric like distance? Indeed, an awesome portion of the literature focuses on simply this. Methods like Heuristic Search Planning (HSP) and Fast-Forward (FF) search to outline heuristics by fixing relaxed variations of the issue, which incorporates eradicating preconditions or destructive results of actions. The de facto normal for state-space search right now is a variant of those strategies named Fast Downward, whose heuristic depends on constructing a causal graph to decompose the issue hierarchically — successfully taking the computational hit up entrance to rework the issue right into a handful of approximate however smaller issues that proves itself worthwhile in follow.

Below is an instance utilizing pyrobosim and the PDDLStream planning framework, which specifies a extra advanced objective that makes use of the predicates we described above. Compared to our instance on this put up, the video under has a couple of refined variations in that there’s a separate class of objects to signify the rooms that the robotic can navigate, and places can have a number of placement areas (for instance, the counter has separate left and proper areas).

• (At robotic bed room)
• (At apple0 table0_tabletop)
• (At banana0 counter0_left)
• (Holding robotic water0)

Alternative search strategies

While ahead state-space search is without doubt one of the commonest methods to plan, it isn’t the one one. There are many various search strategies that search to construct alternate knowledge constructions whose objective is to keep away from the computational complexity of increasing a full state-transition mannequin as above. Some widespread strategies and phrases you will note embody:

In basic, these search strategies are inclined to outperform state-space search in duties the place there are a number of actions that may be carried out in any order relative to one another as a result of they rely upon, and have an effect on, mutually unique components of the world. One of the canonical easy examples is the “dinner date example” which is used to display Graphplan. While these slides describe the issue in additional element, the concept is that an individual is getting ready a dinner date the place the top objective is that dinner and a gift be prepared whereas the home is clear — or (dinner current ¬garb). By interested by the issue on this planning graph construction, we will achieve the next insights:

1. Planning seeks to search out actions that may be executed independently as a result of they’re mutually unique (mutex). This the place the notion of partial ordering is available in, and why there are computational good points in comparison with express state-space search: Instead of individually looking out by means of alternate paths the place one motion happens earlier than the opposite, right here we merely say that the actions are mutex and we will determine which to execute first after planning is full.
2. This downside can’t be solved at one stage as a result of cooking requires clear palms (cleanH) and wrapping the current requires quiet, whereas the 2 strategies of taking out the rubbish (carry and dolly) negate these predicates, respectively. So within the answer under, we should broaden two ranges of the planning graph after which backtrack to get a concrete plan. We first execute prepare dinner to take away the requirement on cleanH, after which carry out the opposite two actions in any order — it doesn’t matter.
3. There is another answer the place on the first stage we execute the wrap motion, and on the second stage we will execute prepare dinner and dolly (in both order) to attain the objective. You can think about this answer could be favored if we moreover required our dinner date hero to have clear palms earlier than beginning their date — gross!

Planning graph for the dinner date downside [Source].
Straight strains are preconditions and results, strains with bins are no-operation (no-op) hyperlinks, and curved strains are mutual exclusion (mutex) hyperlinks.
One answer to the issue is highlighted in blue by backtracking from the objective state.

To carry this all full-circle, you’ll typically discover state-space search implementations that use strategies like Graphplan on a relaxed model of the issue to estimate the fee to objective as a heuristic. If you wish to dig into the main points, I might suggest A Tutorial on Planning Graph-Based Reachability Heuristics, by Daniel Bryce and Subbarao Kambhampati.

Towards extra advanced duties

Let’s get again to our cell robotic instance. What if we wish to describe extra advanced motion preconditions and/or objective specs? After all, we established initially of this put up that straightforward duties in all probability don’t want the large hammer that could be a process planner. For instance, as an alternative of requesting {that a} particular object be positioned at a particular location, we may transfer in the direction of one thing extra basic like “all apples should be on the table”.

New instance world containing objects, apple0 and apple1, which belong to the identical object kind (apple).

To discover this, let’s add predicates denoting objects belonging to classes. For instance, (Type ?t) can outline a particular kind and (Is ?o ?t) to indicate that an object belongs to such a kind. Concretely, let’s imagine that (Type apple), (Is apple0 apple), and (Is apple1 apple).

We can then add a brand new derived predicate (Has ?loc ?entity) to finish this. Derived predicates are simply syntactic sugar — on this case, it helps us to succinctly outline a whole area of attainable states from our library of present predicates. However, it lets us specific extra elaborate concepts in much less textual content. For instance:

• (Has desk apple0) is true if the article apple0 is on the location desk.
• (Has desk apple) is true if a minimum of one object of kind apple is on the location desk.

If we select the objective state (Has desk apple) for our instance, an answer may contain inserting both apple0 or apple1 on the desk. One implementation of this derived predicate may look as follows, which makes use of the exists key phrase in PDDL.

(:derived (Has ?loc ?entity)
(or
; CASE 1: Entity is a particular object occasion, e.g.,
; (Has desk apple0)
(and (Location ?loc)
(Obj ?entity)
(At ?entity ?loc)
)
; CASE 2: Entity is a particular object class, e.g.,
; (Has desk apple)
(exists (?o)
(and (Obj ?o)
(Location ?loc)
(Type ?entity)
(Is ?o ?entity)
(At ?o ?loc)
)
)
)
)

Another instance could be a HasAll derived predicate, which is true if and provided that a specific location incorporates each object of a particular class. In different phrases, if you happen to deliberate for (HasAll desk apple), you would wish each apple0 and apple1 to be relocated. This may look as follows, this time making use of the indicate key phrase in PDDL.

(:derived (HasAll ?loc ?objtype)
(indicate
(and (Obj ?o)
(Type ?objtype)
(Is ?o ?objtype))
(and (Location ?loc)
(At ?o ?loc))
)
)

You may think about additionally utilizing derived predicates as preconditions for actions, to equally add abstraction in different components of the planning pipeline. Imagine a robotic that may take out your trash and recycling. A derived predicate may very well be helpful to permit dumping a container into recycling provided that all of the objects contained in the container are made from recyclable materials; if there’s any non-recyclable object, then the robotic can both select the violating object(s) or just toss the container within the trash.

Below is an instance from pyrobosim the place we command our robotic to attain the next objective, which now makes use of derived predicates to precise places and objects both as particular occasion, or by means of their varieties:

• (Has desk0_desktop banana0)
• (Has counter apple1)
• (HasNone lavatory banana)
• (HasAll desk water)

Conclusion

This put up barely scratched the floor of process planning, but in addition launched a number of assets the place you could find out extra. One central useful resource I might suggest is the Automated Planning and Acting textbook by Malik Ghallab, Dana Nau, and Paolo Traverso.

Some key takeaways are:

1. Task planning requires mannequin and modeling language to allow us to describe a task-agnostic planning framework that may be utilized to a number of duties.
2. Task planning is search, the place the output is a plan, or a sequence of actions.
3. State-space search depends on intelligent heuristics to work in follow, however there are different partial-order strategies that goal to make search tractable differently.
4. PDDL is without doubt one of the commonest languages utilized in process planning, the place a area is outlined because the instrument to unravel a number of issues comprising a set of objects, preliminary state, and objective specification.
5. PDDL isn’t the one technique to formalize process planning. Here are a couple of papers I loved:

After studying this put up, the next ought to now make a bit of extra sense: Some of the more moderen process planning programs geared in the direction of robotics, such because the ROS2 Planning System (PlanSys2) and PDDLStream, leverage a few of these planners talked about above. Specifically, these use Fast Downward and POPF.

One key pitfall of process planning — a minimum of in how we’ve seen it thus far — is that we’re working at a stage of abstraction that’s not essentially excellent for real-world duties. Let’s take into account these hypothetical eventualities:

• If a plan entails navigating between two rooms, however the rooms should not related or the robotic is simply too massive to move by means of, how we do know this earlier than we’re truly executing the plan?
• If a plan entails inserting 3 objects on a desk, however the objects bodily won’t match on that desk, how can we account for this? And what if there’s another mixture of objects that does match and does fulfill our objective?

To tackle these eventualities, there presumably is a technique to introduce extra professional information to our area as new predicates to make use of in motion preconditions. Another is to contemplate a richer area of motion parameters that causes about metric particulars (e.g., particular poses or paths to a objective) extra so than a purely symbolic area would. In each circumstances, we’re considering extra about motion feasibility in process planning. This leads us to the sector generally often known as process and movement planning (TAMP), and would be the focus of the subsequent put up — so keep tuned!

In the meantime, if you wish to discover the cell robotic examples on this put up, try my pyrobosim repository and check out the process and movement planning documentation.

You can learn the unique article at Roboticseabass.com.