Prediction of Future Configurations of a Moving Target in a Time-Varying Environment Using an Autoregressive Model

Author(s)
Ashraf Elnagar

ABSTRACT

In this paper, we describe an algorithm for predicting future positions and orientation of a moving object in a time-varying environment using an autoregressive model (ARM). No constraint is placed on the obstacles motion. The model addresses prediction of translational and rotational motions. Rotational motion is represented using quaternions rather than Euler representation to improve the algorithm performance and accuracy of the prediction results. Compared to other similar systems, the proposed algorithm has an adaptive capability, which enables it to predict over multiple time-steps rather than fixed ones as reported in other works. Such algorithm can be used in a variety of applications. An important one is its application in the framework of designing reliable navigational systems for autonomous mobile robots and more particularly in building effective trajectory planners. Simulation results show how significantly this model could reduce computational cost.

In this paper, we describe an algorithm for predicting future positions and orientation of a moving object in a time-varying environment using an autoregressive model (ARM). No constraint is placed on the obstacles motion. The model addresses prediction of translational and rotational motions. Rotational motion is represented using quaternions rather than Euler representation to improve the algorithm performance and accuracy of the prediction results. Compared to other similar systems, the proposed algorithm has an adaptive capability, which enables it to predict over multiple time-steps rather than fixed ones as reported in other works. Such algorithm can be used in a variety of applications. An important one is its application in the framework of designing reliable navigational systems for autonomous mobile robots and more particularly in building effective trajectory planners. Simulation results show how significantly this model could reduce computational cost.

Cite this paper

nullA. Elnagar, "Prediction of Future Configurations of a Moving Target in a Time-Varying Environment Using an Autoregressive Model,"*Intelligent Control and Automation*, Vol. 2 No. 4, 2011, pp. 284-292. doi: 10.4236/ica.2011.24033.

nullA. Elnagar, "Prediction of Future Configurations of a Moving Target in a Time-Varying Environment Using an Autoregressive Model,"

References

[1] Y. Hwang and N. Ahuja, “Gross Motion Planning—A Survey,” ACM Computing Surveys, Vol. 24, No. 3, 1992, pp. 219-291. doi:10.1145/136035.136037

[2] J.-C. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, London, 1991. doi:10.1007/978-1-4615-4022-9

[3] K. Kant and S. Zucker, “Towards Efficient Trajectory Planning: The Path-Velocity Decomposition,” The International Journal of Robotics Research, Vol. 5, No. 3, 1986, pp. 72-89. doi:10.1177/027836498600500304

[4] K. Fujimura and H. Samet, “Motion Planning in a Dynamic Environment,” Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, 14-19 May 1989, pp. 324-330.

[5] T. Tsubouchi, K. Hiraoka, T. Naniwa and S. Arimoto, “A Mobile Robot Navigation Scheme for an Environment with Multiple Moving Obstacles,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots, Raleigh, 7-10 July 1992, pp. 1791-1798.

[6] T. Fraichard and C. Laugier, “Path-Velocity Decomposition Revisited and Applied to Dynamic Trajectory Planning,” Proceedings of the IEEE International Conference on Robotics and Automation, Atlanta, 2-6 May 1993, pp. 40-45.

[7] A. Basu and A. Elnagar, “Safety Optimizing Strategies for Local Path Planning in Dynamic Environments,” International Journal on Robotics Automation, Vol. 10, No. 4, 1995, pp. 130-142.

[8] P. Fiorini and Z. Shiller, “Time Optimal Trajectory Planning in Dynamic Environments,” IEEE International Conference on Robotics and Automation, Minneapolis, 22-28 April 1996, pp. 1553-1558.

[9] N. Kehtarnavaz and N. Griswold, “Establishing Collision Zones for Obstacles Moving with Uncertainty,” Computer Vision, Graphics and Image Processing, Vol. 49, No. 1, 1990, pp. 95-103. doi:10.1016/0734-189X(90)90165-R

[10] A. Elnagar and K. Gupta, “Motion Prediction of Moving Objects Based on an Autoregresive Model,” IEEE Transactions on SMC, Vol. 28, No. 6, 1998, pp. 803-810.

[11] C. Chang and K. Song, “Dynamic Motion Planning Based on Real-Time Obstacle Prediction,” IEEE International Conference on Robotics Automation, Minneapolis, 22-28 April 1996, pp. 2402-2407.

[12] J. Ortega and E. Camacho, “Mobile Robot Navigation in a Partially Structured Static Environment Using Neural Predictive Control,” Control Engineering Practice, Vol. 4, No. 12, 1996, pp. 1669-1679. doi:10.1016/S0967-0661(96)00184-0

[13] C. Yung and N. Ye, “An Intelligent Mobile Vehicle Navigator Based on Fuzzy Logic and Reinforcement Learning,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 29, No. 2, 1999, pp. 314-321.

[14] A. Foka and P. Trahanias, “Predictive Autonomous Robot Navigation,” IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. 1, 2002, pp. 490-495.

[15] S. Koenig and R. Simmons, “Unsupervised Learning of Probabilistic Models for Robot Navigation,” IEEE International Conference on Robotics Automation, Minneapolis, 22-28 April 1996, pp. 2301-2308.

[16] S. Thrun, “Probabilistic Algorithms and the Interactive Muesuem Tour-Guide Robot Minerva,” International Journal of Robotics Research, Vol. 19, No. 11, 2000, pp. 972-999. doi:10.1177/02783640022067922

[17] C.-H. Tsai, J.-S. Lee and J.-H. Chuang, “Path Planning of 3-D Objects Using a New Workspace Model,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 31, No. 3, 2001, pp. 420-425.

[18] E. Bachmann, I. Duman, U. Usta, R. McGhee, X. Yun and J. Zyda, “Orientation Tracking for Humans and Robots Using Inertial Sensors,” International Symposium on Computational Intelligence in Robotics and Automation, Monterey, 8-9 November 1999, pp. 187-194.

[19] J. Marins, X. Yun, E. Bachmann, R. McGhee and J. Zyda, “An Extended Kalman Filter for Quaternion-Based Orientation Estimation Using Marg Sensors,” International Conference on Intelligent Robots and Systems, Maui, 29 October-3 November 2001, pp. 2003-2011.

[20] K. Shanmugan and A. Breipohl, “Random Signals: Detection, Estimation, and Data Analysis,” John Wiley & Sons, New York, 1988.

[21] S. Kay, “Fundamentals of Statistical Signal Processing: Estimation Theory,” PTR Prentice Hall, Upper Saddle River, 1993.

[22] M. Shensa, “Recursive Least Squares Lattice Algorithms—A Geometric Approach,” IEEE Transactions on Automatic Control, Vol. 26, No. 3, 1981, pp. 695-702. doi:10.1109/TAC.1981.1102682

[23] K. Shoemake, “Animating Rotations with Quaternion Curves,” Computer Graphics, Vol. 19, No. 3, 1985, pp. 245-254. doi:10.1145/325165.325242

[1] Y. Hwang and N. Ahuja, “Gross Motion Planning—A Survey,” ACM Computing Surveys, Vol. 24, No. 3, 1992, pp. 219-291. doi:10.1145/136035.136037

[2] J.-C. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, London, 1991. doi:10.1007/978-1-4615-4022-9

[3] K. Kant and S. Zucker, “Towards Efficient Trajectory Planning: The Path-Velocity Decomposition,” The International Journal of Robotics Research, Vol. 5, No. 3, 1986, pp. 72-89. doi:10.1177/027836498600500304

[4] K. Fujimura and H. Samet, “Motion Planning in a Dynamic Environment,” Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, 14-19 May 1989, pp. 324-330.

[5] T. Tsubouchi, K. Hiraoka, T. Naniwa and S. Arimoto, “A Mobile Robot Navigation Scheme for an Environment with Multiple Moving Obstacles,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots, Raleigh, 7-10 July 1992, pp. 1791-1798.

[6] T. Fraichard and C. Laugier, “Path-Velocity Decomposition Revisited and Applied to Dynamic Trajectory Planning,” Proceedings of the IEEE International Conference on Robotics and Automation, Atlanta, 2-6 May 1993, pp. 40-45.

[7] A. Basu and A. Elnagar, “Safety Optimizing Strategies for Local Path Planning in Dynamic Environments,” International Journal on Robotics Automation, Vol. 10, No. 4, 1995, pp. 130-142.

[8] P. Fiorini and Z. Shiller, “Time Optimal Trajectory Planning in Dynamic Environments,” IEEE International Conference on Robotics and Automation, Minneapolis, 22-28 April 1996, pp. 1553-1558.

[9] N. Kehtarnavaz and N. Griswold, “Establishing Collision Zones for Obstacles Moving with Uncertainty,” Computer Vision, Graphics and Image Processing, Vol. 49, No. 1, 1990, pp. 95-103. doi:10.1016/0734-189X(90)90165-R

[10] A. Elnagar and K. Gupta, “Motion Prediction of Moving Objects Based on an Autoregresive Model,” IEEE Transactions on SMC, Vol. 28, No. 6, 1998, pp. 803-810.

[11] C. Chang and K. Song, “Dynamic Motion Planning Based on Real-Time Obstacle Prediction,” IEEE International Conference on Robotics Automation, Minneapolis, 22-28 April 1996, pp. 2402-2407.

[12] J. Ortega and E. Camacho, “Mobile Robot Navigation in a Partially Structured Static Environment Using Neural Predictive Control,” Control Engineering Practice, Vol. 4, No. 12, 1996, pp. 1669-1679. doi:10.1016/S0967-0661(96)00184-0

[13] C. Yung and N. Ye, “An Intelligent Mobile Vehicle Navigator Based on Fuzzy Logic and Reinforcement Learning,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 29, No. 2, 1999, pp. 314-321.

[14] A. Foka and P. Trahanias, “Predictive Autonomous Robot Navigation,” IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. 1, 2002, pp. 490-495.

[15] S. Koenig and R. Simmons, “Unsupervised Learning of Probabilistic Models for Robot Navigation,” IEEE International Conference on Robotics Automation, Minneapolis, 22-28 April 1996, pp. 2301-2308.

[16] S. Thrun, “Probabilistic Algorithms and the Interactive Muesuem Tour-Guide Robot Minerva,” International Journal of Robotics Research, Vol. 19, No. 11, 2000, pp. 972-999. doi:10.1177/02783640022067922

[17] C.-H. Tsai, J.-S. Lee and J.-H. Chuang, “Path Planning of 3-D Objects Using a New Workspace Model,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 31, No. 3, 2001, pp. 420-425.

[18] E. Bachmann, I. Duman, U. Usta, R. McGhee, X. Yun and J. Zyda, “Orientation Tracking for Humans and Robots Using Inertial Sensors,” International Symposium on Computational Intelligence in Robotics and Automation, Monterey, 8-9 November 1999, pp. 187-194.

[19] J. Marins, X. Yun, E. Bachmann, R. McGhee and J. Zyda, “An Extended Kalman Filter for Quaternion-Based Orientation Estimation Using Marg Sensors,” International Conference on Intelligent Robots and Systems, Maui, 29 October-3 November 2001, pp. 2003-2011.

[20] K. Shanmugan and A. Breipohl, “Random Signals: Detection, Estimation, and Data Analysis,” John Wiley & Sons, New York, 1988.

[21] S. Kay, “Fundamentals of Statistical Signal Processing: Estimation Theory,” PTR Prentice Hall, Upper Saddle River, 1993.

[22] M. Shensa, “Recursive Least Squares Lattice Algorithms—A Geometric Approach,” IEEE Transactions on Automatic Control, Vol. 26, No. 3, 1981, pp. 695-702. doi:10.1109/TAC.1981.1102682

[23] K. Shoemake, “Animating Rotations with Quaternion Curves,” Computer Graphics, Vol. 19, No. 3, 1985, pp. 245-254. doi:10.1145/325165.325242