Trajectory Prediction for Moving Objects Using Artificial Neural Networks

Pierre Payeur, Hoang Le-Huy, Clement M.

Human Factors: The Journal of the Human Factors and Ergonomics Society

Summary

                  Prediction of objects trajectory and position is very important for industrial robots and servo systems, where this kind of information might be used for control, capture and other observation issues.

Parts’ trajectories are often unknown and catching object problem can be useful for example in a typical loading/unloading problem of a robot grasping an object (for instance s box) from a slide or a conveyor.

In such a condition of course accuracy is strictly important, both for achieving the goal and for safety purposes.

An optimum off-line method is path planning based on cubit polynomials with dynamics added (G. Sahar, Hollerbach, 1986), but this method involved a lot of computation and it is done off-line, being not flexible.

The authors propose the use of Artificial Neural Networks (ANN), which can be computed faster and most of all can learn the system, being adaptable and flexible. The problem can be defined as the prediction of the trajectory of a moving object in real time, with minimum error, with no collision on an arbitrary path.

·       Model

Time t₀ is defined as the time in which the manipulator starts moving, the prediction is done with the period of time T. The trajectory model is defined with a cubic function: χ(t)=1/6α₀t³+1/2β₀t²+γ₀t+χ₀, where χ represents the position, orientation, velocity or acceleration according on needs.

Neural network are trained to define the values of the coefficients α₀, β₀, γ₀ at each change of trajectory for which they have to be recalculated, the presence of pre- and post-conditioning allows the need of a long network so that in the end there are 3 inputs, two layers of 20 hidden cells each and one output cell.

The global predictive structure is a multiplication of this basic topology by the number of d.o.f. .The Network is modeled so that it basically obtains information about the change in position and not the exact position, this method ensures reduction of calculations, but pre and post conditioning are then of course required in order to ensure the start and continuation of the calculations. Sampling period T too many times also should be avoided, so the preconditioning module computes differences between the known positions and feeds the network is pseudo-displacement value, so the network will process it and generates the anticipated pseudo-variation of the position or orientation, the post-conditioning module finds then velocity and acceleration through kinematics. The processed data from the neural nets is normalized so that the maximum value is lower than the activation function maxima (in this case a bipolar sigmoidal activation function with a range from -1.0 to 1.0). Between two successive sampling there is a maximum coordinate variation ∆p_max, while limitation in resolution is the minimum detection possible (∆p_resolution), so that the number of possible steps to consider is S_Tsingle=2∆p_max/∆p_resolution+1, which must be globally should be powered by three for each of the inputs. The size of the data can be reduced since two successive position or orientation variation are always of a similar amplitude with a constant sampling rate, so it can be assumed hat there is a maximum difference, tables (Appendix C) help for calculations shown at page 151. Once the input triplet is processed with the cubic model already introduced (to ensure that the output data presented to the network are exact), these are normalized between ±0.8 to avoid extremes, at that point the back-propagation algorithm and the pseudo-random presentation order are used for training the data (triplets are not presented in a fixed order, but the entire set must be used within one epoch).

Key Concepts

Artificial Neural Network, Path Planning, Trajectory Prediction

Conclusion

The method appear to be optimal and working as the polynomial trajectory model but being more flexible. Anticipated values are also more reliable and variances are more similar between axis so that errors could be improved and controlled.

Theory and Application of Neural Networks for Industrial Networks for Industrial Control Systems

Toshio Fukuda, Takanori Shibata

IEEE Transactions on Industrial Electronics, Vol.39,No 6, December 1992

Summary

                  Human’s brain is composed by about 10¹⁰ neurons which allow the brain to be capable of having the following unique characteristics: parallel processing of information, learning function, self-organization capabilities, associative memory and is good for information processing. Ideally researched want to obtain a similar decision making approach and control system for robots, so that artificial neural network basically is a connection of many linear and non linear neuron models and where information is processed in a parallel manner. In the literature there have been approaches in obtaining «mindlike» machines (based on the idea of interconnecting models in the same manner as biological neurons), cybernetics (for which main principles see relationship between engineering principle, feedback and brain function) and the idea of “manufacturing a learning machine”. The literature goes further on in covering recognition system arriving to the Hopfield Net (a series of first-order non-linear differentiable equations that minimize a certain energy function).

·       Models

Each neuron’s output is obtained by summing all the inputs in the same neuron, subtracting the bias and considering a weigh effect on each input. The net is classified in two categories: recurrent net (for which multiple neurons are interconnected) and feed-forward net (which presents a hierarchical structure).

The Hopfield Net is a recurrent net, which has the capability of providing feedback paths, basically with the aim of stabilizing a certain potential field. For the purpose the state of the system and the potential field are used (refer to page 475 for the formulas), the system tends to equilibrium at infinity. This kind of setup allows parallel operation and it’s a case of associative memory (as for the system tends to move to equilibrium points).

Neural Networks are applied in different fields, as for the Travelling Salesman Problem, for which though the only suboptimal solution can be obtained (since the Hopfield transition is based on the least mean algorithm and this may stack to local minimum cases. The Boltzmann Machine is another case of application, for which each neuron is operating with a certain probability, so it also can minimize the energy function as for the Hopfield Net. Further implementations include the Feedforward Neural Network, it’s a back-propagation technique, meaning that is uses gradient search to minimize the error computer as the mean difference between the desired output and the actual one. Once the Back-Propagation is consisting basically the learning face, therefore the overall system first uses the input vector to produce its own output vector, then it computer the difference between the desired output and actual one and adjusts the weights according to the Delta Rule. The initial weights are have to be initialized and random small values are used (for the back propagation algorithm please refer to page 478).

Adaptive Critic appears to be an extended method for learning applications through associative search element and single adaptive critic element (the first being the action network and the latter being the critic network, having as an output a reward or punishment for the first network. Learning method can be offline (carrying unnecessary training), online (problem in initialization), or feedback error learning (which has the issue of lacking of knowledge of the system).

Key Concepts

Artificial Neural Networks, Backpropagation, Delta rule, Robot Learning

Key Results

Neural Networks are applied in vision and speech recognition, design and planning, application control (supervised control, where sensors input information, inverse control, which learns inverse dynamics of a system and neural adaptive control, in order to predict future outputs of a system), knowledge processing (where databases can be use also for initialization and for supervising the net). 

On responsiveness, safety, and completeness in real-time motion planning

Kris Hauser

Autonomous Robots, 2012

Summary

                  Replanning appears to be a powerful mechanism for controlling robot motion under hard constraints and unpredictable disturbances, involving a tradeoff between the planning horizon and its responsiveness to disturbances. A method commonly used is reactively replan at fixed time steps, with the risk of creating a myopic system, therefore adaptive time steps are proposed using “adaptive time stepping with exponential back-off” (ATS-EB), which learn a suitable time step according on whether the planner is able to make progress within the time limit. In order to perform research in this area, key aspect are: correctness, completeness and optimality (with this left for future research). Safety is a big concern in the literature (together with bounded rationality, time stepping issue and speed), Feron et al. introduced the notion of τ-safety, for which a trajectory results safe for at least time τ, establishing a hard deadline for replanning. Petti and Fraichard introduced the notion of “inevitable collision states” (ICS): a state for which no possible control can recover from a collision (using virtual obstacles is can prevent unnecessary explorations).

·       Model

In deterministic environment we the planner generated iteratively subsets of feasible states starting from an initial state at time t₀, planning can be stopped at any time when the trajectory that attains the least value of cost functional C(y) is found, if the planner is given no time limit on any query that admits a solution trajectory, then the planner find a solution in expected finite time. The ATS+EB algorithm (page 38) is supported by two theorems which ensure safety, completeness and competitiveness. The ATS+EB will never drive the robot to unfeasible state and the in a deterministic and perfectly modeled environment, with a reachable goal, it will always find the solution trajectory in finite expected time (which is demonstrated to be loosely bounded at 4NT_mac, where N are the iterations and T_max is the expected running time). Failures of type I are the one which go against the first theorem, therefore for which the global minima may alternate between to locally easy but globally difficult problems, type II errors are those for which the robot gets inadvertently into a dead-end.

In the case of uncertainty no safety guarantees are logically possible, therefore the “time to potential failure” (TTPF) is introduced in the ATS+C algorithm, which manages the replanning time step using this new parameter, keeping the robot safe as long as planning can increase TTPF faster than it is consumed (algorithm at page 43).

If the robot may seek to optimize the potential function V(x), then some degree of safety must sacrificed, since the algorithm seeks to both increase TTPF and improving V(x). The proposed algorithm (page 44) maintains both optimistic and pessimistic trajectory (the role of the pessimistic one, which is followed by default, is to optimize the TTPF, while the the optimistic one guides towards the goal).

In this case again there are two possible failures: type I, consisting of states for which escaping failure is difficult for the planner, type II, consisting in inevitable failure. Increasing the computational power these two errors can be considerably resuced.

Key Concepts

Adaptive time step, replanning

Key Results

The experiments and results prove that using fixed cutoff with windows which are too short provoke unrealiability, since escaping can be possible on local minima, but also an extended windows my be problematic under the point of view of time to achieve the goal. The adaptive strategy appears to be the best except for narrow passages for which it is 45% slower than the best constant cutoff. Replanning is demonstrated to be a viable mechanism for real-time navigation and obstacle avoidance in dynamic environments.