A heuristic framework for path planning the largest volume object from a start to goal configuration

In this article we present a heuristic algorithm to compute the largest volume of an object in three dimensions that can move collision-free from a start configuration to a goal configuration through a virtual environment. The results presented here provide industrial designers with a framework to reduce the number of design iterations when designing parts to be placed in tight spaces.

1 Introduction

Being able to determine whether a virtual object can pass through a virtual environment collision-free is a fundamental problem in virtual design. Depending on the exact problem at hand, there exist hundreds of papers addressing this problem from all sorts of aspects. In this paper we focus on a lesser studied problem of utmost importance for industrial designers. We are interested in being able to compute the largest object than can travel collision-free from a start configuration to a goal configuration. This academic investigation is motivated by numerous real life problems and the basic motivation for this article is the virtual verification and automation of car designs. In particular, one wants to know if a new car design can pass through an assembly line without colliding with other objects and if it does collide, what are the minimal design changes that need to be made to avoid the collisions. This information can also be used for future design problems if the environment and trajectory remain the same (as is typical for factory installations).