University of Birmingham
School of Computer Science
Grasping and Manipulation with a Multi-Fingered Hand
RSMG Report: Thesis Proposal

The systems as mentioned above are referred to in the literature as embedded systems. Many researchers are unified by the belief that such systems in which the interaction between the agent and its environment is a predominant factor should be designed in terms of dynamical systems rather than as composed of two independent objects [41]. In other words, the agent-environment interaction can be viewed as a coupled dynamic system in which the outputs of the agent influence the environment as inputs and the outputs of the environment affect the agent as inputs. In fact, the agent’s outputs are its planned actions which alter the surrounding environment and the environment’s outputs are perceived by the agent’s sensors. As already mentioned, it may be the case that the agent fails to build a complete description of the state of the environment because of either noisy perceptions or a non-static environment which changes asynchronously with respect to the agent’s perception timing. Finally, it is important to note that in embedded systems the future sequence of states of the environment is influenced by the agent’s outputs at each stage.

From the perspective of a designer of intelligent agents for embedded systems, the aforementioned characteristics have several implications. First, an incomplete description of the state of the environment forces the agent to act in partial ignorance. Second, when the environment is not passive and its evolution is not entirely influenced by the agent’s inputs, the agent has an upper bound on the time it takes to decide what to do next. Furthermore, since earlier decisions of the agent may significantly influence its future internal states, the embedded intelligent agent should be designed in terms of an adaptive agent. More precisely, we should take into consideration an adaptive agent’s mapping function from the inputs to outputs. Such a mapping is usually called a policy in literature.

A branch of control theory addresses the set of problems concerning non-static (or dynamic) environments which keep changing through time in a non-deterministic way, supplying methods for building adaptive control policies. These methods define closed-loop control policies which operate in such models specifying the evolution of the system according to the state of the environment and its underlying task. Closed-loop policies are therefore suitable for controlling stochastic systems. Phenomena of the system such as internal state transitions and action outcomes can be modelled as stochastic functions according to a probability density function (pdf) which is usually specific to the domain of application. Furthermore, most of the problems can be expressed assuming that the evolution of the system depends only on the previous internal state and independently of the previous history. This property is known as the Markovian Property and it defines the basic assumption of a rich framework, termed Markov Processes (MP), for embedded systems with stochastic outcomes.

An adaptive agent may learn how to modify its own policy according to either specific domain knowledge or its experience. A way to create a learning agent is to include in the agent’s inputs also some sort of feedback other than an observation of the state of the environment. Feedback may be structured as signals describing correct behaviours and penalising wrong choices. Such a pattern is known as supervised learning and assumes an entity such as a teacher who knows exactly the optimal behaviour. Alternatively, the feedback may evaluate the agent’s policy by some Index of Performance (IoP). In this case, no teachers are necessary and the evaluation is based on some objective criteria which describe merely how good (or bad) the agent’s policy is. The latter approach is useful for a wider range of problems where the optimal behaviour is incognito and it is known as Reinforcement Learning (RL).

In short, reinforcement learning defines a trial and error approach in which the agent learns how to interact with the surrounding environment. The learning is task-dependent. Correct behaviours of the agent receive positive feedback termed reinforcement. Generally, this feedback is a sequence of scalar values that express the ‘‘goodness’’ of a particular behaviour. The mapping between states of the environment and agent’s actions to reinforcement values is known as the reinforcement or reward function.

Littman in [24] describes sing the following examples:

A frog jumps around a barrier to get to a delicious mealworm. A commuter tries an unexplored route to work and ends up having to stop and ask for directions. A major airline lowers prices for its overseas flights to try to increase demand. A pizza-delivery company begins a month-long advertising blitz. These are examples of sequential decision making. [24]

In other words, a frog which plans its behaviour for the next time step in order to achieve its task (eating a delicious mealworm) is a problem that can be formally modelled as sequential decision making. The actions selected by the frog are defined as jumps and its behaviour or policy might be described as the need to jump around the barrier and reach the prey with as few jumps as possible. At any time we expect that our frog will select the best jump in order to go round the obstacle, following as closely as possible the optimal ‘‘trajectory’’ (i.e. the one which requires the fewest number of jumps). The frog will then learn its optimal behaviour by experience, jumping and (succeeding in) eating mealworms; in fact when its policy chooses actions which lead to sub-optimal trajectories it might not capture its prey, discouraging the frog from following such behaviour again.

There is another aspect of the problem that the frog should take into consideration, that is how to execute the selected action. In fact the jump should involve a reliable trajectory which can be actually executed by the frog. In other words, the frog can execute such a jump with the intended force and direction; and the whole trajectory should be in a free space where no obstacle can jeopardise the outcome. In robotics, that is a well known problem that can be solved by a full branch of techniques and algorithms termed in literature as

Recently, progress has been made on the problem of planning motion for robots with many degrees of freedom through complex environments [36, 46, 45, 44, 48, 30, 9, 47, 35, 2, 14, 8, 43, 42, 1]. However, such robots are only used in carefully structured domains, where poses and shapes of objects within the working space of the robot are exactly known a priori. Usually, the environment is assumed to be static which guarantees that its configuration does not change according to external forces. In this case robots are faster and produce a more accurate job than any human. In real-world problems however, such assumptions must be released and the agent needs to infer configurations and dynamics of the surrounding environment using its sensors and previously gathered experience. Sensors provide noisy signals and required calibrations which are difficult to achieve. Anyway, we mainly aim to deal only with the uncertainty on the pose of the object to manipulate. Therefore we will assume our working scenario to be exactly known, except for the initial pose of the object which is inferred using vision sensors. The scenario is also assumed to be static, which means that it is not subject to external forces and it can not change its configuration unless there is an explicit action from the agent. Nevertheless, the dynamics of the system provide further uncertainty to the problem because they are non-linear and hard to approximate. We are also interested to model our system with stochastic dynamics in order to deal with unstructured world¹¹1Probabilistic approaches are not the only ones reliable. E.g. closed-loop policies might be only based on sensor feedback. However, probabilities express our confidence over our current knowledge of the world and may lead to more efficient solutions..

To motivate the methods we aim to use in this thesis, we make the following observation: the fundamental problem of planning in scenarios where the agent needs to interact with its environment by making contacts with (fully or partially) unknown objects is that the configurations of the robot and objects in the world are not exactly known at the time of execution. We therefore plan not only how to change the world with our actions but to change also what we know about the world. In other words, the planner or controller should tell us how confident we are with the representation of relevant aspects of the world, for example whether or not the agent achieved a stable grasp. Consequently our goal is designing a planner which leads to a subset of states where this confidence is maximised in order to optimally solve the intended task. The problem requires the ability to balance confidence maximisation and use of the previously acquired knowledge. Formally, this is termed the

In order to design such a planner, we aim to develop an adaptive agent which learns how to behave in its environment to maximise the expectation of succeed. We aim to express what we know about the uncertain aspects of the world as a belief state, which is the probability density distribution (pdf) over the possible set of world states, and then select actions according to the current belief state. In other words, we will use a stochastic approach to model uncertainties. The agent will then have to find the optimal action or control input which maximises our expectation of completing the task. Therefore we will attempt to solve the problem of grasping and manipulation using algorithms and techniques from the

As a concrete example of how such a model might look like, we consider a simple instance of the game of Battleship. This is a wildly used example in A.I. community (see e.g. [15]). In our tiny example, we play a 2 by 3 scheme, one-side Battleship. The goal is to destroy the only 2-block ship in the scheme. The left side of Figure 1 shows our example on which the ship is placed in A2 and B2. In the beginning, the agent has no clue where the ship could be. Therefore, the agent might act guessing C3 as first ‘‘shot’’ and then observe a ‘‘miss’’. Successively it might guess B2 and observe a ‘‘hit’’. A feasible way to express our knowledge of the problem after the second observation is as a probability distribution over possible displacements of the ship, which is our belief state. The right side of Figure 1 shows our belief state after these two actions. In fact after observing a ‘‘hit’’ only two displacements are possible for the ship, each with probability of 1/2. We now expect that the player selects the next action according to the current belief state, which will be B1 or A2 with same probability.

As also shown in [15], we might want to use the same representation to describe a different problem. We can easily imagine that the ship in our Battleship example might be a sitting object on a table. The goal now is to achieve a stable grasp of the object. In this case, the agent perceives the world by noisy sensors (e.g. vision system) and the initial uncertainty about the pose of the object might be high enough to make traditional open-loop plans (even extended with simple feedback) not reliable. We therefore aim to reduce the initial uncertainty applying information gathering actions which lead to maximise the likelihood of success. However, differently from the Battleship example, our object is unlikely to be only in few discrete locations on the table and touching the object in order to estimate better its pose can cause it to move.

[24] [17], described in detail in Section 3.2, are a popular framework to solve decision making problems with uncertainty. In order to solve exactly a POMDP is necessary to compute off line a policy which describes the optimal agent’s behaviour for any possible state of the problem. For example, it is possible to reason in terms of POMDP formulation to model the Battleship problem previously proposed. Figure 2 shows how the search tree for the Battleship example looks like. The tree is trunked at the third level which defines the situation after two moves. The state labeled as $S_{2}$ identifies our current situation after observing a ‘‘hit’’ in B2, where four actions are available but only two of them are feasible. The off line POMDP solver would extend the root with all possible evolutions of the game to return a policy which identifies the best action according to the previous history of the game. In literature a precise evolution of the problem as the one shown in Figure 2 with the sequence of states $<S_{0},S_{1},S_{2}>$ is often termed as

Many real problems, therefore, are not suitable for this kind of approach because they present large or continuous state, action and observation spaces. Although some approximations techniques have been developed (see i.e. [34]), the state-of-the-art of planning in high-dimensional continuous spaces would require us to draw only a random subset of possible trajectories in the solution space and follow the most promising one to reach a possible final configuration. Such a method is known as nd has been applied successfully also to problems model as POMDPs [32]. In this work, the policy is computed on line alternating planning phase to execution phase in order to alleviate computational complexity focusing only on local policies. In fact, online approaches are forward search rooted in the current belief state; such approach does not guarantee optimality but reduces the branching factor of the search because it only needs to consider the reachable belief states from the current belief state. Although different optimization methods have been proposed and good performance has been reached for many difficult problems, as in $9\times 9$ Go [10], these methods are based on look-ahead strategies which involve prediction on the most likely system evolutions. Consequently, it is hard to model long-term trajectories in systems with strong uncertainty related to the actions’ outcome.

Platt et al. in [29] propose a formalization of the problem of grasping in unstructured environments as SLAG can be viewed as a belief space control problem. In other world, this formalization allows them to figure out a sequence of motor control actions for grasping while bounding the probability of failure. This approach has been applied to a real scenario on which the robot needs to localise and grasp a box. Two boxes of unknown dimension are presented to the robot. This situation is challenging because the displacement of the two boxes might make harder the problem of identifying the exact pose of the boxes themselves. In their example, the robot is equipped with two paddles and it has a pre-programmed ‘‘lift’’ function. The robot localises objects using a laser sensor mounted on its left wrist. The boxes, however, are assumed to be placed at a known height and thus the robot has uncertainty only in one dimension.

Hsiao et alii in [16] show a tactile-driven exploration of the environment to maximise the expected confidence relative to the object pose before attempt a grasp. In this work, the set of actions is parameterised with the current belief state over the object’s pose. A fixed number of actions for gathering information and grasp are pre-computed offline. The planner solves the POMDP on line selecting gathering information actions which reduce the uncertainty about the object’s pose until a threshold of confidence has been reached, and then the pre-computed grasp action is executed. If the belief state after all the gathering information actions correctly approximate the real object’s pose, the grasp has high probability to succeed.

Hauser in [13] and [12] present a sample-based replanning strategy for driving partially observable, high-dimensional robotic systems to a desired configuration. The planning algorithm uses forward simulation of randomly sampled open-loop controls in order to build a search tree in the belief space. At any time the search tree is rooted on the current belief state. Then the algorithm select the action from the root which leads to the best evaluated node in the tree. The procedure is repeated until the goal region is reached. Hauser performed experiments on two scenarios: a 2D pursuit scenario with 4D state space; and a localisation scenario in a known $d$-dimensional environment, on which the convergence of the algorithm has been demonstrated up to 7 dimensions.

We are interested to solve the grasping problem using online strategies as Hsiao et al. do, but without the limitation of a fixed set of actions. We will rather sample random actions at planning time, and we will evaluate our belief state according to the executed simulations.

In this thesis, we address to solve the problem of planning with uncertainty in stochastic environments using reinforcement learning techniques. Section 3 discusses in more detail our approach.

The grasping scenario we have been working on is composed as follows:

1. 1.

   Kuka arm KR 5 sixx R850 6DOF

2. 2.

   DLR-Hand II prototype of five-fingered hand;

3. 3.

   a camera for vision capture;

4. 4.

   torque sensors on all finger joints;

5. 5.

   force torque sensors at wrist;

6. 6.

   a known object to be manipulated.

The pushing scenario we have been working on is composed as follows:

1. 1.

   5-axis Katana 6M180 arm equipped with a spherical probe as end effector;

2. 2.

   a camera for vision capture;

3. 3.

   6-axis force torque sensor at the base of the end effector;

4. 4.

   a known object to be manipulated (polyflap).

Such a division should show how the grasping and manipulation problem could be split in order to define the problem space of my thesis. The subtasks are as follows:

1. 1.

   attempt a stable grasp;

2. 2.

   move objects from one configuration to another on a table;

3. 3.

   move objects, held and supported entirely by the hand, from one configuration to another with respect the frame of the hand (in-hand manipulation).

This report is structured as follows:

• •

  section 2 describes the problem domain of planning with uncertainty for autonomous robotic manipulators;

• •

  section 3 first introduces models for path planning in high-dimension continuous spaces and models for planning with uncertainty. It then presents how to use specific domain knowledge to obtain better performance and, finally, it shows some hybrid models we have taken inspiration from for our proposed solution;

• •

  section 4 first introduces some technical detail specific of our domain and then shows formally our approach.

• •

  section 5 describes how we will evaluate the performance of our algorithms.

Grasping an object involves (1) determining a set of contact points for the fingers on the surface of the object in order to achieve a stable grasp; (2) planning a trajectory of the arm to bring the hand in a pre-grasp position where it is possible to conclude the grasp by closing the fingers; and (3) a finger closing strategy which copes with the kinematic constraints of the hand.

The problem of grasping objects is an hard challenge for many reasons. First of all, even for known objects and a given grasp it is hard to define in an analytic way the exact configuration of the hand for which only the expected surfaces collide in the predicted way. It is obviously more difficult when objects are unknown or partially visible: for example, how to predict whether or not an unknown mug has an handle on the opposite side with respect to the camera? Additionally, planning for grasping requires to model a sequence of non-trivial physic interactions between fingers/palm of the robot hand and the object as, for example, precocious contacts which modify in somehow the world configuration making inadequate the pre-computed planning.

The manipulation of an object with a robotic multi-fingered hand can be split into three different categories: (1) single finger manipulation (or pushing); (2) multi-finger manipulation of an object on a stable surface; and (3) in-hand manipulation of an object held and supported entirely by the hand. The single finger manipulation concerns simple pushing an object from a robotic arm using a simple end-effector which generates only a single point of contact with the object. In this case, the aim is to plan a sequence of actions (or pushes) to move the object from an initial pose to a desired one. The multi-finger manipulation on a stable surface can be seen as an extension of the case described above where multiple contacts are allowed. However, it is not a trivial extension because the result of a combination of actions applied at the same time is generally different from what we would obtain applying the same sequence of actions separately. However in-hand manipulation involves manipulating an object within one hand. The fingers and the thumb are used to best position the object for the required activity, for example, picking up a pen and moving it into the position with your fingers for writing. In other words, in-hand manipulation is the result of a combination of forces (or pushes) applied by several fingers to a target object in order to achieve a desired object pose.

All these manipulations necessitate the ability to predict how objects behave under finger manipulation and, furthermore, the ability to plan a sequence of actions to move the object from the initial pose to the desired one. At the time of writing this report, we are developing a simple path planner to cope with a physical environment and to achieve a desired pose of a given object using single finger pushing operations.

The Probabilistic RoadMap (PRM) [18] [11] planner is a motion planning algorithm in robotics, which solves the problem of determining a path between a starting configuration of the robot and a goal configuration whilst avoiding collisions.

The basic idea behind PRMs is to take random samples from the configuration space of the robot, test them for whether they are in free space, and use a local planner to attempt to connect these configurations to other nearby configurations. The starting and goal configurations are added in, and a graph search algorithm is applied to the resulting graph to determine a path between the starting and goal configurations.

The probabilistic roadmap planner consists of two phases: a construction and a query phase. In the construction phase, a roadmap (graph) is built, approximating the motions that can be made in the environment. First, a random configuration is created which is then connected to some neighbours, typically either the k nearest neighbours or all neighbours less than some predetermined distance. Configurations and connections are added to the graph until the roadmap is dense enough. In the query phase, the start and goal configurations are connected to the graph, and a path is obtained using Dijkstra’s shortest path query.

The main disadvantage of the PRM is that this model seems impractical for many problems with non-holonomic²²2A system is non-holonomic if the controllable degrees of freedom are fewer than the total degrees of freedom constraints.

A Rapidly-exploring Random Tree (RRT) [22] [23] is a data structure and algorithm that is designed for efficiently searching non-convex high-dimensional spaces. RRTs are constructed incrementally in a way that quickly reduces the expected distance to a randomly-chosen point in the tree. RRTs are particularly suited for path planning problems that involve obstacles and differential constraints (non-holonomic or kino-dynamic). RRTs can be considered as a technique for generating open-loop trajectories for nonlinear systems with state constraints. An RRT can be intuitively considered as a Monte-Carlo way of biasing search into the largest Voronoi regions.

Unlike PRMs, RRTs cope well with non-holonomic constraints. However, both techniques do not model the uncertainty of the environment in a primitive way. Recently, some techniques have been developed to make RRTs work in uncertain worlds. These techniques are discussed in the section 3.3.1. Additionally, PRMs is not designed to explore a continuous space seeking for a possible solution. PRMs are used to grow multiple distributed trees and can be used for multiple queries to find path between two given points. The underlying assumption is that the goal position is not part of the tree and should be known as well as the initial position. Whilst, RRTs is a proper exploring algorithm which is able to explore high-dimensional spaces seeking for the point which satisfies all the problem constraints.

An Markov Decision Problem (MDP) [24] [17] is a model of an agent interacting synchronously with a world. As shown in Figure 5, the agent takes as input the state of the world and generates as output actions which themselves affect the state of the world. In the MDP framework, it is assumed that, although there may be a great deal of uncertainty about the effects of an agent’s actions, there is never any uncertainty about the agent’s current state, it has complete and perfect perceptual abilities.

A discrete stochastic process is defined by a set of random variables $\{X_{t},t\in\mathcal{T}\}$, where $\mathcal{T}=\{0,1,2,\dots\}$ is the set of possible times and $X_{t}$ denotes the ouotcome at the $t^{th}$ stage or time step. The domain of $X_{t}$ is the set of all the possible outcomes denotes $\mathcal{S}=\{s_{1},s_{2},\dots,s_{|\mathcal{S}|}\}$ A MDP can be described as a tuple $\langle\mathcal{S},\mathcal{U},\tau,\rho\rangle$, where

• •

  $\mathcal{S}$ is a finite set of states of the world;

• •

  $\mathcal{U}$ is a finite set of actions;

• •

  $\tau\colon\mathcal{S}\times\mathcal{U}\rightarrow\Pi(\mathcal{S})$ is the state transition function, giving for each world state and agent action, a probability distribution over the world’s states;

• •

  $\rho\colon\mathcal{S}\times\mathcal{U}\rightarrow\Re$ is the reward function, giving the expected immediate reward gained by the agent for taking each action in each state.

In accordance with the Markov property, the next state and the expected reward depend only on the previous state and the action taken; even if it conditions the additional previous states, the transition probabilities and the expected rewards would remain the same. While the MDP addresses the problem of choosing optimal actions in completely observable stochastic domains [40], we need a model more suited with uncertainty. For example, in the grasping problem, once the robot has perceived the object to grasp (using vision and the 3D geometric features) and computed a path to reach the pre-grasp position, the robot should define and plan a sequence of actions to close the fingers in a proper way to maximize the likelihood of successful grasp. For doing this, the robot needs a formal model of sequential decision making which describes the environment with which it interacts and the behavior it exhibits. Furthermore, this model should be able to cope with uncertainty because the world around the robot has perceived using noisy sensors. In practice, we are considering the problem of choosing optimal actions in partially observable stochastic domains. Problems like the one describe above can be modeled as Partially Observable Markov Decision Processes (POMDPs)  [24] [17]. In POMDPs, the system interacts with a stochastic environment whose state is only partially observable. Actions change the state of the environment and lead to numerical penalties/rewards, which may be observed with an unknown temporal delay. The model aims to devise a policy for action selection that maximizes the reward.

Formally, a POMDP can be formalized as a tuple $\langle\mathcal{S},\mathcal{U},\mathcal{Y},\tau,\rho,\psi\rangle$, where $\mathcal{S},\mathcal{U},\tau$ and $\rho$ keep the same definition aforementioned. In addition:

• •

  $\mathcal{Y}$ is a finite set of observations;

• •

  $\psi\colon\mathcal{S}\times\mathcal{U}\rightarrow\Pi(\mathcal{Y})$ is the observation function, giving for each world state and agent action, a probability distribution over the set of observations;

Obviously, the POMDP framework embraces a large range of practical problems. However, solving a POMDP is often intractable except for small problem due to their computational complexity: finite-horizon POMDPs are PSPACE-complete [28] and infinite-horizon POMDPs are undecidable [25].

This section describes hybrid models on which path planners for high-dimensional spaces are extended to cope with partial ignorance or approximate POMDP approaches are applied to high-dimensional continuous spaces.

Robot kinematics is the study of the motion of a robot in terms of purely geomerical contraints( i.e. leaving aside considerations of the relationship between forces, inertias and accelerations). A serial robot arm can be modeled as an open chain of links connected by (typically rotatable) joints. In a kinematic analysis, the position, velocity and acceleration of points on an open chain of links are computed without considering the forces that cause the motion. Instead, typically, the positions and velocities of an end effector are related to angles and angular velocities at the robot’s joints. Robot kinematics also deals with aspects of redundancy, collision avoidance and singularity avoidance. We mainly have two types of robotic kinematics, namely: (1) forward or direct kinematics and (2) inverse kinematics. The former determines the position of the robot’s end effector with respect to a global frame of reference, given the length of each link and the angle of each joint. The latter, on the other hand, computes the angle which each joint should assume to deliver the robot’s end effector to a desired global position, given the length of each link.

With reference to the robotic manipulation and grasping, let $\mathcal{C}$ be the set of all possible configurations of the object to be manipulated with respect to a global frame of reference $\mathcal{O}$. Any point $p\in\mathcal{C}$ is expressed as $p=[R_{\mathcal{O}}t_{\mathcal{O}}^{T}]$, where $R_{\mathcal{O}}\in\Re^{3\times 3}$ is a rotation matrix and $t_{\mathcal{O}}\in\Re^{3}$ is a transition vector, both over the $x$, $y$ and $z$ axis with respect to $\mathcal{O}$. Hereafter we also refer to this set as the working space. The working space should not be confused with the configuration or joint space $\mathcal{J}$, of a robotic device which defines the set of all possible configurations that the robot can assume but express in joint angles. To make this point clearer, figure 12 shows all the joints of a 6-DOF articulated or jointed arm robot. Any configuration of the robot can be expressed by a 6-dimensional vector which specifies the angles each joint should assume.

Let $\mathcal{M}=\langle\mathcal{X},\mathcal{U},\mathcal{Y},\tau,\psi,\rho\rangle$ be a POMDP model, where:

• •

  $\mathcal{X}$ defines configurations of the environment express as the pose of the object and of the agent in working space $\mathcal{C}$;

• •

  $\mathcal{U}$ defines movements of the agent in joint configuration space $\mathcal{J}$;

• •

  $\mathcal{Y}$ defines observations of the object’s pose;

• •

  $\tau\colon\mathcal{X}\times\mathcal{U}\rightarrow\Pi(\mathcal{X})$ defines the state transition function;

• •

  $\psi\colon\mathcal{X}\times\mathcal{U}\rightarrow\Pi(\mathcal{Y})$ defines the observation function;

• •

  $\rho\colon\mathcal{X}\times\mathcal{U}\rightarrow\Re$ defines the cost function to minimise;

Figure 13 shows the real pushing scenario with the Katana 6M180 arm, its spheric end effector which is used as a robotic finger and the L-shape object termed polyflap which will be manipulated by the robot. All our knowledge about the environment configuration is inferred by the camera which captures the position and orientation of the L-shape object, termed polyflap, with reference to a global frame at each time step $t$.

Such models are computationally intractable mainly for the following reasons:

1. 1.

   high-dimensional continuous state space;

2. 2.

   non-linear transition and observation functions;

The state space $\mathcal{X}$ requires a high representational cost which depends directly on the complexity of the agent. In other words, the greater the number of the robot’s joints, the higher the dimension of $\mathcal{X}$ will be. As mentioned in section 2, the principal uncertainty is in the configuration of the robot and the state of the objects in the world, that is formally represented by the set $\mathcal{X}$. Furthermore, the high-dimensional state space also means that many parameters must be set in order to properly describe the system evolution. Additionally, uncertainty related to the outcomes of robot actions, make it impossible to define analytical or deterministic transition and observation functions.

Our proposed solution can be summarised as follows:

1. 1.

   use of a black box simulator for POMDPs instead of an analytic model;

2. 2.

   deterministically define the system evolution according to a set of local information-based control policies;

More specifically, we plan to use a simulated physic environment (see section 3.3.3) as a black box simulator for POMDPs rather than an explicit probability distribution over states, actions and observation spaces. Then, according to the authors of [32], we only need to define a reward or cost function in order to accurately drive the system towards an optimal solution. We propose to use a switching control policy as described in section 3.2.3. The switching policy should be considered the high-level planner, whilst at the low level we define a set of local information-based policy which specifies the system evolution. Each local policy considers only one cost (or equivalently reward) function and at any time only one local policy can be selected by the high-level planner. Hence the evolution of the system is deterministically computed drawing a finite number of reachable belief points from the current belief point and selecting the one which minimises (maximises) the current cost (reward) function.

Appendix A presents the original RRT algorithm (algorithm 3) as defined in [22], whilst the algorithms 4 5 6 define our first attempt at applying RRTs to the problem of pushing manipulation. As described in RMSG Report 2, our principal modification to the original algorithm lies in the algorithm 5 which implements a simple heuristic-driven substitute for an inverse model. In short, we select an action to extend nodes of the tree by moving the finger along the straight line which connects the central of mass of the object to the current target point, which we hope to add to the tree. This implementation is simplistic since it does not encode any information about the orientation or rotation motions of the object, and ignores certain aspects of the object’s shape. Nevertheless, it showed good results for cubic shaped objects, but extends poorly to other objects, e.g. the polyflap object which can tip or topple as well as slide.

In order to improve the simple, early version of our algorithm, we propose to re-implement algorithm 5 as an adaptive controller. Like the POMCP algorithm (see section 3.3.2), we define the stochastic embedded system as a black box simulator for the POMDP model and the agent’s belief is updated by using a Monte-Carlo technique. In a different way, we do not use rollout techniques to explore trajectories in the solution space. Instead we design some sensor-feedback policies, as define in section 3.2.3, to directly explore the optimal area of the solution space. Algorithm 1 shows in pseudo-code our modified implementation of the basic RRT algorithm. The algorithm iteratively constructs an RRT $T$, rooted in the beginning state configuration $x_{init}$, until the goal configuration is reached with a maximum of $K$ vertices.

Algorithm 2 shows the pseudo-code of the adaptive controller. So far, the proposed algorithm has been implemented only in terms of a single pushing scenario and briefly can be expressed as follows: at time $k$, the RRT algorithm randomly selects a point in the continuous working space, defined as rotation and translation with respect to a reference frame. At this stage, we are able to compute a metric distance, which takes into account either angular or linear distance, between the current pose of the object and the desired one. The agent then considers some random actions (sampled according to some heuristic for the time being) to make the object move. Each such action is trialled in a physics simulator to predict what it’s outcomes might be. If the agent realises that an action’s outcome is increasing the metric distance, the action is immediately discarded. On the other hand, if the action’s outcome produces any improvement, the action is continued until a local minima of the cost function is reached. A fixed number of actions are explored at each iteration, and only the one which minimises the cost function is executed by the controller at time $k$, thus extending the RRT tree as close as possible towards the next new node requested by the RRT algorithm.