Thursday , June 21 2018

Using Particle Filters to Find
Free Obstacle Trajectories for a Kinematic Chain

Alejandro REYES-AMARO1, Alejandro MESEJO-CHIONG1,
Ramon Mas-SANSO2, Antoni JAUME-I-CAPO2
1 Facultad de Matemática y Computación, Universidad de la Habana, Cuba,
2 Departament de Ciències Matemàtiques i Informàtica,
Universitat de les Illes Balears, Spain,

Abstract: The problem of finding an appropriate path for a mechanical arm that tries to reach a target among obstacles is one of the most important in fields of automation and robotics. It is both a classic inverse kinematics and collision detection problem. This project aimed to construct a tool to plan a path for an articulated arm through a two-dimensional environment with obstacles. The inverse kinematics problem is addressed by heuristics Bayesian particles filter, and the collision detection problem is solved using computational geometry methods for calculating the free configurations space. The proposed tool has a graphical interface with which you can get information from the designed experiments. The feasibility of this approach and its advantages in complex two-dimensional environments is shown. We proved that good results can be obtained with an appropriate selection of the parameters.

Keywords: Inverse kinematics, particle filters, configuration-free space, path planning.

>>Full Text
Alejandro REYES-AMARO, Alejandro MESEJO-CHIONG, Ramon Mas-SANSO, Antoni JAUME-I-CAPO, Using Particle Filters to FindFree Obstacle Trajectories for a Kinematic Chain, Studies in Informatics and Control, ISSN 1220-1766, vol. 22 (2), pp. 185-194, 2013.


Many automated processes today require to solve the problem of planning a set of movements for an articulated arm with the objective of reaching a specific goal and avoiding obstacles without using neither sensors nor other technologies [15], but knowing its spatial information. These articulated arms are formally designated as kinematic chains. A Kinematic chain is formed by a set of rigid bodies (links or segments) joined at the ends by articulations that allow for certain types of movement, mainly translation, rotation or revolution. One end of the chain remains fixed whilst the other end reaches the defined objective; the latter is called end-effector.

Using a geometrical approach we can easily compute the position and orientation of a given segment from the values of the preceding articulations (direct or forward kinematics). Let us say that in an articulated chain as the human arm we can easily compute the situation of a fingertip given the angles of all the articulations from the clavicle to the finger. However, the inversion of this model (inverse kinematics) becomes difficult due to the non-linearity of the governing equations. Let suppose that we want to infer the values of the angles configuration space that will locate our end-effector in a given position (situation space).

The problem of controlling a kinematic chain has been first posed in robotics [17] although it has also been widely used in computer graphics [2, 6]. Robotic structures are most of the times well-known mechanisms with a moderated number of degrees of freedom so it is relatively easy to derive an analytical solution. Nevertheless, more complex kinematic chains face the additional problem of being under constraint or redundant – i.e. they contain more d.o.f. than required for a class of tasks. In this case, instead of using a closed-form or an analytical solution we should use a more general approach for the positioning and manipulation of kinematic chains like resolved motion rate control. Resolved motion rate control is an Inverse Kinematics technique based on the inversion of the Jacobian matrix. This approach allows the manipulation of an articulated figure with a relatively low computational cost and using intuitive specifications, however it also has known drawbacks as singularities and local minima solutions.

The problem becomes even more complex when obstacles have to be avoided. Several solutions have been proposed in the literature using a broad variety of techniques like direct kinematics [14], neural networks [17], genetic algorithms [1] or heuristic solutions [8, 16] or solving optimization problems [13].

We work in rehabilitation environments where the user is required to reach a goal avoiding virtual obstacles. The arm of the user is modeled with a kinematic chain and we want to automatically compute the optimal path to perform such a task.

In such a context, singularities a local minima have to be prevented [4, 5]. We propose to solve inverse kinematics by means of extending heuristic solutions based on particle filter techniques combined with the computation of trajectories among obstacles. We want to prove its feasibility in complex two-dimensional situations in a controlled development environment.

The rest of this paper is organized as follows. The problem definition is stated in section 2. The section 3 shows how to use the particle filters to solve the inverse kinematic problem. Section 4 describes the stages that a kinematic chain goes through. The method to calculate the trajectory of the end-effector is presented in section 5. In section 6 experimental results are discussed and the section 7 is reserved to present the conclusions of the work.


  1. ABO-HAMMOUR Z. S., A. G. ASASFEH, A. M. AL-SMADI, O. M. K. ALSMADI, A Novel Continuous Genetic Algorithm for the Solution of Optimal Control Problems. Optim Control Applied Methods, vol. 32, 2011, pp. 414-432.
  2. BAERLOCHER, P., An Inverse Kinematic Architecture Enforcing an Arbitrary Number of Strict Priority Levels. Visual Computation, vol. 20(6), 2004, pp. 402-417.
  3. BIRD, R. H., P. LU, J. NOCEDAL, C. ZHU, A Limited Memory Algorithm for Bound Constrained Optimization. Technical Report NAM-08 1994.
  4. BUSS, S. R.: Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoinverse and Damped Least Squares methods. Department of Mathematics, University of California San Diego USA, 2004.
  5. BUSS, S. R., J. S. KIM, Selectively Damped Least Squares for Inverse Kinematics. Department of Mathematics Department of Computer Science, University of California San Diego, USA, 2004.
  6. CARY, P. B., J. ZHAO, N. I. BADLER, Interactive Real-time Articulated Figure Manipulation using Multiple Kinematic Constraints. SIGGRAPH Comput Graph, vol. 24(2), 1990, pp. 245-250.
  7. CORDERO, Y., OCSolv: un sistema con estrategia adaptativa para Problemas de Control Optimal. Facultad de Matemática y Computación, Universidad de La Habana, La Habana, Cuba, 2010.
  8. COURTY, N., E. ARNAUD, Sequential Monte Carlo Inverse Kinematics. INRIA Rapport de recherche 2007, p. 6426.
  9. DE-BERS, M., M. VAN-KREVEL, M. OVERMARS, O. SCHUARZKOPF, Computational Geometry Algorithms and Application, 2nd edition; 2000.
  10. DOUCET, A., A. M. JOHANSEN, Tutorial on Particle Filtering and Smoothing: Fifteen Years Later. Institute of statistical mathematics, Tokyo, Japan Department of Statistic, University of Warwick, UK, 2008.
  11. JOHNSON, M. P., Exploiting Quaternions to Support Expressive Isteractive Character Motion. Massachusetts Institute of Technology USA PhD Thesis, 2003.
  12. LIU, D. C., J. NOCEDAL, On the Limited Memory BFGS Method for Large Scale Optimization. Mathematical Programming, vol. 45, 1989, pp. 503-528.
  13. PORTILLO-VELEZ, R. D. J., C. A. CRUZ-VILLAR, A. RODRIGUEZ-ANGELES, On-line Master/Slave Robot System Synchronization with Obstacle Avoidance. Studies in Informatics and Control, ISSN 1220-1766, vol. 21(1), 2012, pp. 17-26.
  14. SCIAVICCO, L., B. SICILIANO, A Solution Algorithm to the Inverse Kinematic Problem for Redundant Manipulators. Robotics and Automation, vol. 4(4), 1988, pp. 403-410.
  15. SUSNEA, I., VASILIU, G., On Using Passive RFID Tags to Control Robots for Path Following. Studies in Informatics and Control, ISSN 1220-1766, vol. 20(2), 2011, pp. 157-162.
  16. SUSNEA, I., G. VASILIU, A. FILIPESCU, A. RADASCHIN, Virtual Pheromones for Real-Time Control of Autonomous Mobile Robots. Studies in Informatics and Control, ISSN 1220-1766, vol. 18(3), 2009, pp. 233-240.
  17. ZHANG, Y., J. WANG, Obstacle Avoidance for Kinematically Redundant Manipulators using a Dual Neural Network. Systems, Man, and Cybernetics, Part B: Cybernetics, 34(1), 2004, pp. 752- 759.