Convex hull representations of models for computing collisions between multiple bodies |
| |
| Institution: | 1. Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, USA;2. Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721, USA;3. Department of Systems Engineering, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia;1. Department of Mechanical Engineering, School of Engineering, Sripatum University, 2410/2 Phaholyothin Rd., Jatujak, Bangkok 10900, Thailand;2. Durham School of Architectural Engineering and Construction, University of Nebraska-Lincoln, Omaha, NE, USA;1. Ecole Normale Superieure de Lyon, Lyon, France;2. Università degli Studi di Bergamo, Bergamo, Italy;1. Department of Veterinary Medicine, Obihiro University of Agriculture and Veterinary Medicine, Nishi 2-11 Inada-cho, Obihiro, Hokkaido, 080-8555, Japan;2. Department of Reproductive Immunology and Pathology, Institute of Animal Reproduction and Food Research, Polish Academy of Sciences, Olsztyn, 10-748, Poland;3. Department of Life and Food Sciences, Obihiro University of Agriculture and Veterinary Medicine, Nishi 2-11 Inada-cho, Obihiro, Hokkaido, 080-8555, Japan;4. Museum of Natural History, University of the Philippines Los Baños, Laguna, 4031, Philippines;5. College of Veterinary Medicine, University of the Philippines Los Baños, Laguna, 4031, Philippines;6. Department of Biomedical Science, Graduate School of Agricultural and Life Sciences, The University of Tokyo, 1-1-1 Yayoi, Bunkyo-ku, Tokyo, 113-8657, Japan;7. Faculty of Veterinary Medicine, Okayama University of Science, 1-3 Ikoino-oka, Imabari, Ehime, 794-8555, Japan;8. Research and Education Center for Prevention of Global Infectious Diseases of Animals, Tokyo University of Agriculture and Technology, 3-5-8 Saiwai-cho, Fuchu, Tokyo, 183-8509, Japan;9. Laboratory of Sustainable Animal Environment, Graduate School of Agricultural Science, Tohoku University, 232-3 Yomogida, Naruko-onsen, Osaki, Miyagi, 989-6711, Japan |
| |
| Abstract: | In this paper, we consider a collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of S.Z. Selim and H.A. Almohamad European Journal of Operational Research 119 (1) (1999) 121–129], and compare the relative effectiveness in solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear segment. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the effectiveness of solving a sequence of mathematical programs for each time segment over a global programming scheme which considers all segments at once. We provide computational results to illustrate the effect of various numbers of bodies present in the collision scenarios, as well as the times at which the first collision occurs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
