Optimal hypercube algorithms for robot configuration space computation

John Jenq, Wing Ning Li

Research output: Contribution to conferencePaperResearchpeer-review

2 Citations (Scopus)

Abstract

Computing the configuration space is an important problem in spatial planning for robotics applications. In this paper, we present parallel algorithms for computing the configuration space by using hypercube multiprocessors. The digitized images of the obstacles and the robot are stored in an N×N image plane. In this paper, we develop optimal hypercube algorithms to compute the configuration space for circle and rectangle shaped robots. We also develop several new basic hypercube operations. The time complexity of all the algorithms is O (logN) and is asymptotically optimal for hypercube computers. The space complexity of each processor is O (1) which is again optimal.

Original languageEnglish
Pages182-186
Number of pages5
StatePublished - 1 Jan 1995
EventProceedings of the 1995 ACM Symposium on Applied Computing - Nashville, TN, USA
Duration: 26 Feb 199528 Feb 1995

Other

OtherProceedings of the 1995 ACM Symposium on Applied Computing
CityNashville, TN, USA
Period26/02/9528/02/95

Fingerprint

Robots
Parallel algorithms
Robotics
Planning

Cite this

Jenq, J., & Li, W. N. (1995). Optimal hypercube algorithms for robot configuration space computation. 182-186. Paper presented at Proceedings of the 1995 ACM Symposium on Applied Computing, Nashville, TN, USA, .
Jenq, John ; Li, Wing Ning. / Optimal hypercube algorithms for robot configuration space computation. Paper presented at Proceedings of the 1995 ACM Symposium on Applied Computing, Nashville, TN, USA, .5 p.
@conference{c828c7d0c4fe4b3b91762d94cd3b1d15,
title = "Optimal hypercube algorithms for robot configuration space computation",
abstract = "Computing the configuration space is an important problem in spatial planning for robotics applications. In this paper, we present parallel algorithms for computing the configuration space by using hypercube multiprocessors. The digitized images of the obstacles and the robot are stored in an N×N image plane. In this paper, we develop optimal hypercube algorithms to compute the configuration space for circle and rectangle shaped robots. We also develop several new basic hypercube operations. The time complexity of all the algorithms is O (logN) and is asymptotically optimal for hypercube computers. The space complexity of each processor is O (1) which is again optimal.",
author = "John Jenq and Li, {Wing Ning}",
year = "1995",
month = "1",
day = "1",
language = "English",
pages = "182--186",
note = "null ; Conference date: 26-02-1995 Through 28-02-1995",

}

Jenq, J & Li, WN 1995, 'Optimal hypercube algorithms for robot configuration space computation' Paper presented at Proceedings of the 1995 ACM Symposium on Applied Computing, Nashville, TN, USA, 26/02/95 - 28/02/95, pp. 182-186.

Optimal hypercube algorithms for robot configuration space computation. / Jenq, John; Li, Wing Ning.

1995. 182-186 Paper presented at Proceedings of the 1995 ACM Symposium on Applied Computing, Nashville, TN, USA, .

Research output: Contribution to conferencePaperResearchpeer-review

TY - CONF

T1 - Optimal hypercube algorithms for robot configuration space computation

AU - Jenq, John

AU - Li, Wing Ning

PY - 1995/1/1

Y1 - 1995/1/1

N2 - Computing the configuration space is an important problem in spatial planning for robotics applications. In this paper, we present parallel algorithms for computing the configuration space by using hypercube multiprocessors. The digitized images of the obstacles and the robot are stored in an N×N image plane. In this paper, we develop optimal hypercube algorithms to compute the configuration space for circle and rectangle shaped robots. We also develop several new basic hypercube operations. The time complexity of all the algorithms is O (logN) and is asymptotically optimal for hypercube computers. The space complexity of each processor is O (1) which is again optimal.

AB - Computing the configuration space is an important problem in spatial planning for robotics applications. In this paper, we present parallel algorithms for computing the configuration space by using hypercube multiprocessors. The digitized images of the obstacles and the robot are stored in an N×N image plane. In this paper, we develop optimal hypercube algorithms to compute the configuration space for circle and rectangle shaped robots. We also develop several new basic hypercube operations. The time complexity of all the algorithms is O (logN) and is asymptotically optimal for hypercube computers. The space complexity of each processor is O (1) which is again optimal.

UR - http://www.scopus.com/inward/record.url?scp=0029204015&partnerID=8YFLogxK

M3 - Paper

SP - 182

EP - 186

ER -

Jenq J, Li WN. Optimal hypercube algorithms for robot configuration space computation. 1995. Paper presented at Proceedings of the 1995 ACM Symposium on Applied Computing, Nashville, TN, USA, .