Capturing Multilayered Design Intent using Efficient Constraint Decomposition

这个项目处理有效的生成鲁棒，最优计划递归分解几何约束系统为子系统，其解决方案可以重组。主要考虑的是在CAD/CAM的交互设计和装配环境中出现的约束系统。分解几何约束系统是一个关键且长期存在的问题，因为解决系统的压倒性成本是由一般代数/数值解算器直接求解的最大子系统的大小决定的，并且是指数级的，即不需要进一步分解。此外，一个真正的交互式CAD环境允许约束模型在整个设计过程中与设计师以及下游生产软件进行交互。因此，约束系统的层次结构分解在捕获设计意图方面起着关键作用。由于缺乏高效和鲁棒的分解技术，目前还没有有效的空间变分约束求解器，装配求解器也受到严重限制。这种不足严重阻碍了智能、交互式CAD系统的发展。初步结果为本项目提供了坚实的基础。更具体地说：1)我们已经分离并精确形式化了最优分解重组（DR）规划问题，以及几个新的性能指标，这些指标反映了DR计划和专门针对CAD/CAM的规划者的各种理想特征。dr问题的精确形式化以及新的性能度量具有独立的兴趣，并且具有被约束求解和CAD社区广泛应用的潜力。2)我们开发了一种新的DR规划的构建模块，称为改进的前沿算法（Modified Frontier Algorithm， MFA），它在几个新的性能度量以及初步实现方面显著改进了现有的方法。该项目的总体目标是开发和实现一个完整的DR-planner原型，以及围绕MFA骨干网构建的所需接口，该原型在所有新的性能度量方面都表现良好。此外，原型实现将被纳入Erep系统，然后通过与现有的约束求解器、草图绘制器和CAD系统进行比较来评估。具体的研究任务是为了确保新的DR规划具有各种能力，如：1)处理非几何约束的能力，特别是反映设计意图的方程和参数约束；2)结合设计师指定的多层概念分解的能力，以及对约束系统进行交互更改的鲁棒性和适应性；3)输出DR-plan的最优复杂度和保证近似因子；4)保持CAD约束模型视图与产品主模型的多个（可能是专有的）下游应用视图的一致性的能力；5)实现的模块化，与现有代数/数值求解器的兼容性，以及与现有CAD系统的可合并性。

This project deals with the efficient generation of robust, optimal plans for recursively decomposing geometric constraint systems into subsystems whose solutions can be recombined. Primary consideration is given to constraint systems that arise within the context of interactive design and assembly for CAD/CAM. Decomposing a geometric constraint system is a critical and longstanding issue, since the overwhelming cost in solving the system is dictated by - and exponential in - the size of the largest subsystem that is solved by a general algebraic/numeric solver directly, i.e, without further decomposition. Moreover, a truly interactive CAD environment allows the constraint model to interact with the designer as well as with downstream production software throughout the design process. Hence a hierarchical structural decomposition of the constraint system plays a key role in capturing design intent. Due to the lack of efficient and robust decomposition techniques, there are currently no effective, spatial variational constraint solvers, and assembly solvers are seriously limited. This inadequacy severely hinders the development of intelligent, interactive CAD systems.Preliminary results provide a strong foundation for this project. More specifically: 1) We have isolated and precisely formalized the optimal decomposition-recombination ( DR) planning problem as well as several new performance measures that reflect the various desirable characteristics of DR plans and planners specifically for CAD/CAM. The precise formalization of the DR-problem as well as the new performance measures are of independent interest and have the potential to be widely used by the constraint solving and CAD communities. 2) We have developed the building blocks of a new DR planner, called the Modified Frontier Algorithm (MFA), which significantly improves on existing methods both in terms of several of the new performance measures, as well as in preliminary implementations.The overall goal of the project is to develop and implement a fully-fledged prototype of a DR-planner along with the required interfaces built around the MFA backbone, which performs well with respect to all of the new performance measures. In addition, the prototype implementation will be incorporated into the Erep system and then evaluated by comparison with existing constraint solvers, sketchers and CAD systems.Specific research tasks are directed towards ensuring that the new DR planner possesses various capabilities such as: 1) ability to deal with nongeometric constraints, particularly equational and parametric constraints which reflect design intent; 2) ability to incorporate a multilayered conceptual decomposition specified by the designer, and robustness and adaptability to interactive changes made to the constraint system; 3) optimal complexity, and guaranteed approximation factor of the near-optimal, output DR-plan; 4) ability to maintain consistency of the CAD constraint model view with multiple, possibly proprietary, downstream application views of the product master model; and 5) modularity of the implementation, compatibility with existing algebraic/numeric solvers, and incorporability into existing CAD systems.