運動規劃的目的是幫機器人找出適合的一連串連續的動作，舉例來說，避免碰撞
障礙物，搬移物品到目的地，或是返回充電站。最常見的兩種運動規劃演算法為
PRM 和RRT，其中PRM 是多次查詢的方法，而RRT 通常用來進行單次查詢。
在這篇論文中我們提出一種基於支持向量機的運動規劃方法，稱之為SVMP。
SVMP 主要的優點是大幅的降低執行碰撞偵測的次數，而加快建立路標地圖的速
度。SVMP 建立出的路標地圖可以讓機器人保持在離障礙物最遠的地方移動。而
SVMP 將被與PRM 和RRT 在不同的環境下執行來進行效能比較。

A standard motion planning problem tries to create feasible moves of robot in
order to achieve the objectives, such as avoiding obstacles, delivering items, returning
to the charging stations, etc. Often continuous motion of a robot is handled
as paths in the high dimensional configuration space. Previously two types of planners,
probabilistic roadmap (PRM) and rapidly-exploring random tree (RRT), are
used to compute proper motion of a robot, where PRM is generally used as a multiquery
planner, while RRT is considered as a single-query planner. This paper
proposes a motion planning framework based on support vector machine(SVM)
called SVMP. One main advantage of SVMP is it reduces the number of initial
guesses of feasible robot poses, thus decreases the time in executing local planners
in most roadmap-based methods in complex environments. By employing
SVM techniques into the planner, SVMP takes the global obstacle distribution into
account and generates a roadmap of robot motion that tends to be pushed away
from obstacles. The effectiveness and efficiency of SVMP are compared with
PRM and RRT through experiments in environments with different complexities.

[1] L. Kavraki, P. Svestka, J. Latombe, and M. Overmars, ``Probabilistic
roadmaps for path planning in high-dimensionalconfiguration spaces,'' IEEE
transactions on Robotics and Automation, vol. 12, no. 4, pp. 566--580, 1996.
[2] G. Song, S. Thomas, and N. Amato, ``A general framework for PRM motion
planning,'' in IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND
AUTOMATION, vol. 3, pp. 4445--4450, IEEE; 1999, 2003.
[3] R. Bohlin and L. Kavraki, ``Path planning using lazy PRM,'' in IEEE International
Conference on Robotics and Automation, vol. 1, pp. 521--528, IEEE;
1999, 2000.
[4] C. L. Nielsen and L. E. Kavraki, ``A two level fuzzy prm for manipulation
planning,'' in In Proceedings of the International Conference on Intelligent
Robots and Systems, pp. 1716--1722, 2000.
[5] G. Song, S. Miller, and N. Amato, ``Customizing PRM roadmaps at query
time,'' in IEEE International Conference on Robotics and Automation, vol. 2,
pp. 1500--1505, IEEE; 1999, 2001.
[6] S. LaValle, ``Rapidly-exploring random trees: A new tool for path planning,''
tech. rep., TR 98-11, Computer Science Dept., Iowa State University, 1998.
[7] S. LaValle and J. Kuffner, ``Rapidly-exploring random trees: Progress and
prospects,'' in Algorithmic and computational robotics: new directions: the
fourth Workshop on the Algorithmic Foundations of Robotics, p. 293, AK Peters,
Ltd., 2001.
[8] J. Kuffner Jr and S. LaValle, ``RRT-connect: An efficient approach to singlequery
path planning,'' in Robotics and Automation, 2000. Proceedings.
ICRA'00. IEEE International Conference on, vol. 2, pp. 995--1001, IEEE,
2002.
[9] J. Bruce and M. Veloso, ``Real-time randomized path planning for robot
navigation,'' in RoboCup 2002: Robot Soccer World Cup VI, pp. 288--295,
Springer, 2003.
[10] S. Rodriguez, X. Tang, J. Lien, and N. Amato, ``An obstacle-based rapidlyexploring
random tree,'' in Proceedings 2006 IEEE International Conference
on Robotics and Automation, 2006. ICRA 2006, pp. 895--900, 2006.
[11] C. Chang and C. Lin, ``LIBSVM: a library for support vector machines,'' 2001.
[12] B. Boser, I. Guyon, and V. Vapnik, ``A training algorithm for optimal margin
classifiers,'' in Proceedings of the fifth annual workshop on Computational
learning theory, pp. 144--152, ACM, 1992.
[13] C. Cortes and V. Vapnik, ``Support-vector networks,'' Machine learning,
vol. 20, no. 3, pp. 273--297, 1995.
[14] R. Geraerts and M. Overmars, ``Sampling and node adding in probabilistic
roadmap planners,'' Robotics and Autonomous Systems, vol. 54, no. 2,
pp. 165--173, 2006.
[15] M. Branicky, S. LaValle, K. Olson, and L. Yang, ``Quasi-randomized path
planning,'' in Robotics and Automation, 2001. Proceedings 2001 ICRA. IEEE
International Conference on, vol. 2, pp. 1481--1487, IEEE, 2001.
[16] K. Fang, D. Lin, P. Winker, and Y. Zhang, ``Uniform design: theory and application,''
Technometrics, pp. 237--248, 2000.
[17] K. Fang and D. Lin, ``Uniform Design in Computer and Physical Experiments,''
The Grammar of Technology Development, pp. 105--125, 2008.
[18] http://www.math.hkbu.edu.hk/UniformDesign.
[19] ``Cgal, Computational Geometry Algorithms Library.'' http://www.cgal.org.
[20] N. Amato, O. Bayazit, L. Dale, C. Jones, and D. Vallejo, ``Choosing good
distance metrics and local planners for probabilistic roadmap methods,''
Robotics and Automation, IEEE Transactions on, vol. 16, no. 4, pp. 442--
447, 2000.
[21] T. Lozano-Perez, ``Automatic planning of manipulator transfer movements,''
Systems, Man and Cybernetics, IEEE Transactions on, vol. 11, no. 10,
pp. 681--698, 1981.
[22] Lozano-Perez., ``Spatial planning: A configuration space approach,'' IEEE
transactions on computers, pp. 108--120, 1983.
[23] N. Amato, O. Bayazit, L. Dale, C. Jones, and D. Vallejo, ``Obprm: An
obstacle-based prm for 3d workspaces,'' Robotics: the algorithmic perspective,
pp. 155--168, 1998.
[24] K. Hauser and V. Ng-Thow-Hing, ``Multi-modal motion planning for precision
pushing on a humanoid robot,'' Motion Planning for Humanoid Robots,
p. 251, 2010.