Share PDF

Search documents:
  Report this document  
    Download as PDF   
      Share on Facebook

Scheduling for Autonomous Ikea Furniture Assembly

Raghavendra Srinivasan

School of EECS, Massachusetts Institute Of Technology


In this paper, I am trying to explain the concept behind the scheduling of various low level tasks involved in building Ikea furniture. This algorithm is used to implement the assembly of various furniture using multi robot control and parallel processing of tasks assigned using mobile manipulation.

1 Introduction

Robotics has made tremendous progress in the last four decades in terms of design of manipulation systems and deployment of mobile robots. However, limited progress has been reported in mobile manipulation, primarily due to lack of adequate platforms. The required combination of power, weight and real-time control has not been available until recently. Today it is possible to access light weight arms, and there are a number of mobile platforms that are small and powerful enough to use with a manipulation system. Use of such systems allows for a variety of new applications both in terms of manufacturing as well as service robotics to assist people in everyday situations. A challenge in the design of such systems is tight integration to achieve real-time performance. There are quite a few methods available for construction of systems but very few have considered the integration for real applications. To study this problem, we selected a scenario where the robots have to assemble Ikea furniture. The robots used are KUKA Youbots. In many real-world applications this might not be a realistic platform, but it is an ideal setup to truly demonstrate the challenges of mobile manipulation.

Related Work

There has been a significant amount of previous work on addressing a variety of mobile manipulation tasks. Some early work on behavior-based mobile manipulation was done using a platform named Herbert,7 which is a statically stable mobile base equipped with a custom built arm. This robot is capable of searching cluttered human environments for soda cans and grasping them.

Additional work on behavior-based controller architectures for mobile manipulation was done by Petersson which was later expanded upon formal methods for sequencing complex tasks and assigning processes to

resources were established in the Distributed Control Architecture for the application of mobile manipulation. Petersson et al. have emphasized scalability and availability in a real-time system by using a tree hierarchy with as much local computation and spatial locality as possible.

About Our Project

The Autonomous Ikea furniture assembly is a venture aimed at achieving autonomous assembly of Ikea furniture by building a mobile manipulation system.

The ultimate goal of the autonomous Mobile Manipulation is the execution of complex manipulation tasks, in an unstructured, unplanned and dynamic environments, in which cooperation with humans may be vital. These systems must perform a variety of tasks, acquire new skills, and apply these skills in appropriate situations. They must be able to continually adapt and improve their performance with changes in their environment.

To meet the above requirements, versatile robotic systems must be equipped with many actuators and sensors, resulting in high-dimensional state spaces.

There also lies a lot of uncertainty in these kinds of systems, i.e. the ability to move around, the required generality in the sequence of task execution, and the usages of multiple sensors and actuators, make it impractical to figure out the entire environment for the task. As a result, mobile manipulation systems have to enumerate the problems that arise due to the uncertainty of sensing and actuation and plan to solve them in their solution.

Every system is really complex and requires coordination of a lot of entities including perception, manipulation, control, planning and real time data management.

2 System Architecture

The Ikea furniture assembly system has a very versatile architecture. It makes use of almost all the possible ways of making a Robust and ideal mobile

manipulation system. The system is broken down into 7 entities as shown in the diagram below.

Figure 1: System Architecture showing dependencies and functions.

Each of the above entities has its own prime importance in the system.

Symbolic Planner - The symbolic planning module provides a high-level execution plan to the robotic system, leading it from the environment's initial state to one which qualifies as completion.

Scheduler – The scheduler receives high level operations from the symbolic planner, breaks them down to low level operations, schedules them with respect to the global timeframe and assigns task consisting of abstract components to the master controller.

Master Controller - The Master Controller will receive primitive tasks from the scheduler and assign the abstract components to concrete physical components in the real world and send the resulting fully specified tasks to the manipulation and navigation subsystems. It will also receive status reports from the robots and inventory, and will inform the scheduler of changes in the world state.

Inventory – The goal of the inventory module is to provide the other modules with information about the pose, visibility, bounding box, grasping points and attachment points of various parts and the robots. It also has to connect the camera system to the real world.

Navigation and Inverse Kinematics – The goal of Navigation in this module is to provide controlled navigation in the workspace when asked for it. As the name says, Inverse Kinematics, uses inverse kinematics to control the 5-DOF robotic arm. It provides manipulation with control over arm.

Manipulation - This module is the interface between controller and the real world, with feedback from perception and control through navigation.

Perception - This module basically acts as the backbone for manipulation by giving it information about

the status of the connections made and also by detecting and confirming the right parts being used.

My work in this project is confined to the design of the scheduler, so I will be discussing that in detail.

3 Problem Statement

To break down the high level tasks received from the master controller break them down into lower level tasks and assign tasks to the master controller at appropriate times to achieve desired outcome.


•The Scheduler receives only high level instructions from the symbolic planner.

•The probability of failure of a task assigned to the Master controller is zero.

•The Scheduler receives task status from the master controller.

•Master Controller is capable of processing multiple tasks assigned.


To solve the problem, a Non-Deterministic Finite Automaton was built and it was converted into a Deterministic Mealy Finite state machine by using Powerset construction. Furthermore, hierarchical state machine that is capable of generating dynamic states depending upon the task completed was also implemented.

A nondeterministic finite automaton (NFA) or nondeterministic finite state machine is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined. Although the DFA and NFA have distinct definitions, a NFA can be translated to equivalent DFA using powerset construction, i.e., the constructed DFA and the NFA recognize the same formal language.

The powerset construction applies most directly to an NFA that does not allow state transformations without consuming input symbols (aka: "e-moves"). Such an automaton may be defined as a 5-tuple (Q, S, T, q0, F), in which Q is the set of states, S is the set of input symbols, T is the transition function (mapping a state and an input symbol to a set of states), q0 is the initial state, and F is the set of

accepting states. The corresponding DFA has states corresponding to subsets of Q. The initial state of the DFA is {q0}, the (one-element) set of initial states. The transition function of the DFA maps a state S (representing a subset of Q) and an input symbol x to the set T(S,x) = ∪{T(q,x) | q ∈ Q}, the set of all states that can be reached by an x-transition from a state in S. A state S of the DFA is an accepting state if and only if at least one member of S is an accepting state of the NFA.

Figure 2: An Example of conversion of an NFA into a DFA .

Moving further, a hierarchical state machine, is basically a state machine consisting of various state machines. Implementation of this, enabled the usage of dynamic state creation.

Figure 3: An example of hierarchical state machine with depth equal to two. More complex ones can be made by increasing depth.

6 Implementation

First of all, each output that is to passed to the master controller has to contain 4 components.

•UUID - Universally unique identifier, is intended to uniquely identify information in a distributed environment without significant central coordination. It can be used to tag objects with very short lifetimes, or to reliably identify very persistent objects across a network.

•Instruction – The task that manipulation has to complete at that particular state

•Robot Name – The name of the robot which has to follow the instruction. ( Every robot has its own capabilities, features and specifications, so it has to be used for the job it is designed for.)

•Parameters – Various part types involved in the instruction being passed and also the abstract part names for the respective parts.


The UUID was generated by using a random string generator and was remembered with a particular instruction as a group to verify the completion on receiving the completion status.


To decide the next instruction depending on the present state, a powerset was built taking the following inputs into consideration.

Q(The set of states) => Set of Manipulation Operations

S(The set of input symbols) => {Symbolic planner instruction, Master Controller task status,

internal ID} T(The state transition function) => T(q,x) | q ∈ Q and x is a set of input symbols. q0 (Initial State) => Waiting for Symbolic Planner Instruction.

F(set of Accepting States) => f (symbolic planner instruction)

Robot Name

The robot name was made a function of states and the option of multiple state transition was implemented. This allowed parallel instruction processing.

Figure 4: An example output of Paralel instruction assignment to different robots.


The Parameters were decided depending upon the instruction being passed, also, the dynamic state creation was made possible by assigning a new name everytime an object switched states. In this case, every object had 2 states – mobile and stationary. A new name was assigned to an object once it switched states.

7 Outcome

The outcome of the implementation is a completely reliable scheduler that can assure the completion of an assigned high level task, with negligible delay in instruction passing.

Figure 5: Sample output showing all the functions Implemented.

Figure 6: Sample output showing successful integration with the symbolic planer.

Figure 7: Sample output showing successful integration with the inventory.

8 Conclusion

The Scheduler can provide high level instruction parsing with parallel assignment of tasks for the assembly of table and train set of Ikea furniture.

9 Futurework

A lot of future work can be done in scheduling. At the moment, the scheduler assumes zero probability of error, but, error detection and recovery can be made possible.

Robot Independent scheduling can be made possible if all the robots are of the same kind.

Uniform assignment of tasks to the robots can be made possible. ( This can reduce the time for which furniture is built.)

10 References

[1]Mobile Manipulation,

[2]Hierarchical state Machine, temachine.htm

[3] Powerset Construction,