Robot path planning using intersecting convex shapes: Analysis and simulation
- 1 April 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Robotics and Automation
- Vol. 3 (2), 101-108
- https://doi.org/10.1109/jra.1987.1087080
Abstract
An automated path planning algorithm for a mobile robot in a structured environment is presented. An algorithm based on the Quine-McCluskey method of finding prime implicants in a logical expression is used to isolate all the largest rectangular free convex areas in a specified environment. The free convex areas are represented as nodes in a graph, and a graph traversal strategy that dynamically allocates costs to graph paths is used. Complexity of the algorithm and a strategy to trade optimality for smaller computation time are discussed.Keywords
This publication has 8 references indexed in Scilit:
- Natural decomposition of free space for path planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Constructing the visibility graph for n-line segments in O(n2) timeInformation Processing Letters, 1985
- Path Relaxation: Path Planning for a Mobile RobotPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Solving the find-path problem by good representation of free spaceIEEE Transactions on Systems, Man, and Cybernetics, 1983
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- Minimization of Boolean Functions*Bell System Technical Journal, 1956
- A Way to Simplify Truth FunctionsThe American Mathematical Monthly, 1955
- The Problem of Simplifying Truth FunctionsThe American Mathematical Monthly, 1952