본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

형상 추론과 기하학적 검색 기반의 다단계 경로 계획
Multi-Stage Path Planning Based on Shape Reasoning and Geometric Search

황용구   (정보통신대학교 디지털 미디어 랩  ); 조경래   (동서울대학 기계공학부UU0000473  );
  • 초록

    전통적인 경로 계획기는 로봇의 최적 경로를 찾기 위해 광대한 기하학적 검색을 수행한다. 완전성이 있는 경로계획기는 만약 해가 존재하면 반드시 찾아야 한다. 때문에 많은 검색 시간을 소요하여 해를 찾든지, 아니면 해가 없는 경우에는 없다고 증명을 하여야 함으로 역시 많은 시간을 소요한다. 그러나 인간의 경우는 대부분의 경우에 충돌 회피 경로가 있는지 없는지 빨리 파악할 수 있는 능력을 가지고 있으며, 극단적으로 어려운 문제들을 제외하고는 무둔 경우의 수를 나열하지 않고도 쉽게 해를 찾는다. 본 연구의 목표는 이러한 인간의 사고 능력을 알고리즘화하여, 이동로봇의 운동 경로를 보다 빠르게 찾거나, 아니면 컴퓨터의 계산자원을 낭비하지 않고 일찍이 포기하게 한다. 다각형 환경과 다각형 로봇에 대한 경로계획에, 정량적인 형상 추론과 광대한 기하학적 검색을 결합한 새로운 경로 계획 방법을 제시한다. 제시되어진 알고리즘은 울타리 검증을 통해 해가 없는지를 먼저 검색하고, 만약에 해가 있으면, 정량적인 추론을 통해서 해를 찾고, 그래서 해가 존재하지만 해를 찾을 수 없으면, 완전 검색 알고리즘으로 해를 찾게 된다. 본 연구의 기여는 여러 개의 능률적인 기하학적 검사를 통해, 많은 계산량의 완전 알고리즘을 가능하면 사용하지 않고 해를 찾거나 해가 없음 증명하여, 운동 계획기의 평균 계산량을 최소화한다.


    A novel approach for path planning of a polygonal robot is presented. Traditional path planners perform extensive geometric searching to find the optimal path or to prove that there is no solution. The computation required to prove that there is no solution is equivalent to exhaustive search of the motion space, which is typically very expensive. Humans seems to use a set of several different path planning strategies to analyse the situation of the obstacles in the environment, and quickly recognize whether the path-planning problem is easy to solve, hard to solve or has no solution. This human path-planning strategies have motivated the development of the presented algorithm that combines qualitative shape reasoning and exhaustive geometric searching to speed up the path planning process. It has three planning stages consisting of identification of no-solution cases based on an enclosure test, a qualitative reasoning stage, and finally a complete search algorithm in case the previous two stages cannot determine of the existence of a solution path.


  • 주제어

    경로 계획 .   정량적 형상 추론 .   서비스 로봇 .   주행.  

  • 참고문헌 (16)

    1. J. Lengyel, M. Reichert, B. R. Donald, and D. P. Greenberg, "Real-Time Robot Motion Planning Using Rasterizing Computer Graphics Hardware," Computer Graphics, vol. 24, no. 4, pp. 327-335, August 1990. 
    2. T. Lozano-Prez, J. L. Jones, E. Mazer, P. A. O'Donnell, E. L. Grimson, P. Tournassoud, and A. Lanusse, "Handey: A Robot System that Recognizes, Plans, and Manipulates," IEEE Int. Conf. on Robotics and Automation, pp. 843-849, Raleigh, NC, 1987. 
    3. H. Noborio, T. Naniwa, and S. Arimoto, "A Feasible Motion Planning Algorithm for a Mobile Robot on a Quadtree Representation," Proceedings of IEEE International Conference on Robotics and Automation, pp. 327-332, Scottsdale, AZ, 1989. 
    4. C. Urmson and R. Simmons, "Approaches fro heuristically biasing RPT growth," Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 1178-1183, Las Vegas, Nevada, 2003. 
    5. J. T. Schwartz and M. Sharir, "On the Piano Movers' Problem: II. Techniques for Computing Topological Properties of Real Algebraic Manifolds," Courant Institute of Mathematical Sciences, Report No. 39, 1981. (also in Advances in Applied Mathematics, no. 4, pp. 298-351, 1983) 
    6. L. Yang and S.M. Lavalle, "An improved randon neighborhood graph approach," Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 254-259, Washington DC, 2002. 
    7. Takno Asano, Tetsuo Asano, L. Guibas, J. Hershberger, and H. Imai, "Visibility-Polygon Search and Euclidean Shortest Path," 26th Symposium on Foundations of Computer Science, pp.155-164. 1985. 
    8. J. Barraquand and J. C. Latombe, "A Monte-Carlo Algorithm for Path Planning with Many Degrees of Freedom," Proceedings of IEEE International Conference on Robotics and Automation, pp. 1712-1717, Cincinnati, OH, 1990. 
    9. J. F. Canny, The complexity of motion planning, THe MIT Press, Cambridge, MA, 1988. 
    10. P. C. Chen and Y. K. Hwang, "SANDROS: a Dynamic Graph Search Algorithm for Motion Planning," IEEE Transactions on Robotics and Automation, Vol. 14, No. 3, pp. 390-403, Feb 1998. 
    11. K. K. Gupta, "A 7-dof practical motion planner based on sequential framework: theory and experiments," IEEE Int. Symp. on Assembly and Task Planning, pp. 213-218, Pittsburgh, PA, 1995. 
    12. Kamal Gupta and Angel P. Del Pobil, "Practical Motion Planning in Robotics Current Approaches and Future Directions," John Wiley & Sons, Chichester New York, 1998. 
    13. Y. K. Hwang and N. Ahuja, "Gross Motion Planning - A Survey," ACM Computing Surveys, vol. 24, no. 3, pp. 219-292, September 1992. 
    14. Y. K. Hwang and P. C. Chen, "A Heuristic and Complete Planner for the Classical Mover's Problem," Proc. of IEEE International Conference on Robotics and Automation, pp. 729-736, Nagoya, Japan, 1995 
    15. L. Kavraki and J. C. Latombe, "Randomized preprocessing of configuration space for fast path planning," IEEE Int.-Conf.-on Robotics and Automation, pp.-2138-2145, San Diego, CA, May 1994. 
    16. J. C. Latombe, "Robot motion planning," New York: Kluwer Academic Publishers. 1991. 

 저자의 다른 논문

  • 조경래 (1)

    1. 2011 "집기-놓기 작업을 위한 이동 머니퓰레이터의 자세 선정" 로봇학회논문지 = The journal of Korea Robotics Society 6 (4): 344~352    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기