Simulation-Based Design Program
ARPA/
Lockheed
by
Mark R. Cutkosky
cutkosky@cdr.stanford.edu
Charles J. Petrie
petrie@cdr.stanford.edu
Center for Design Research
Stanford University
560 Panama Street
Stanford, CA 94305-2232
415/725-0162
FAX 725-8475
The current lack of technology for coordinating design decisions and managing change over the life of a product creates higher costs, longer cycle times, and poorer quality than is currently possible.
A key requirement for both managing the development process and for maintaining and modifying the product over its life is the ability to capture decisions and their supporting rationales and to automatically propagate the effects of those decisions in the context of changing requirements, objectives, and constraints.
Our approach to addressing this problem consists of four parts:
In addition to keeping track of the design process, there is the potential to improve such activities as manufacturing process planning and inspection planning by treating them as part of the overall design/product development process. By including the product features in the planning process and using the revision capabilities of Redux, it is possible to improve overall project management and to promote concurrent engineering.
The ``history based" approach of Redux' can be particularly powerful if combined with approaches for representing and propagating the effects of constraints in a design. Much of design (and planning/scheduling) involves the imposition and satisfaction of constraints (e.g., on weight, geometric tolerances, operating temperatures, etc.). Various constraint satisfaction problem (CSP) solvers have been developed over the years and demonstrated to be powerful tools for addressing special design and planning problems. However, no single CSP solver addresses the range of constraints (e.g., discrete, continuous, algebraic, logical) encountered in the design of complex artifacts. A ``constraint manager" or broker is therefore needed to map between between constraints as expressed in the design and as represented by CSP solvers and to identify which CSP solver(s) are can most effectively deal with which sets of constraints.
An additional requirement for design is to capture the relationship between constraints and the rationale for design decisions. Constraints change during the life of the project and it is problematic to track them and their effect on the project process and design. However, Redux can be used to track these constraint changes and their effect on the design and process. Further, Redux can be integrated with the CSP manager to generate design rationales as needed.
NEDL, along with the Redux', CM, and PM agents will constitute the delivered Next-Link framework. We will develop this framework in an agent-based software design, using the SBD architecture and standards of CORBA and KQML (with KAPI), so that the CM can be used with a wide variety of engineering software services.
We also plan to use the DesignRoadmap[Park] to model the tasks and features of the engineering processes to be managed. In addition to using the advanced functionality of this model, including abstraction layers, this will allow us to integrate a quality control mechanism (The on-going work of Maria Yang on Distributed Quality Function Deployment uses the DesignRoadmap process model and the ``House of Quality'' matrix concept to provide a quality assurance process for design decision making within the MECE environment) with the design rationales, constraint satisfaction, and project management services.
Finally, we will develop these services in the context of the MECE electronic notebook, improving these services as necessary, and as a result of experience gained in the ME210 class. We will take the approach of developing an Electronic Design Notebook Language (EDNL), consistent with NEDL, that will be flexible enough to support a variety of utilities and be more powerful than an HTML-based approach. MECE will be extended to generate EDNL statements that can be used by wrapper software to send NEDL messages to the Redux', Constraint Manager (CM), and Project Manger (PM) agents, as well as any other specialized agent services.
We expect this work to require a minimum of three years to produce a useful prototype. However, we can provide a demonstration ``proof of concept'' model of constraint integration within the first six (6) months. With an additional fourth year, we believe that we perform additional technology transfer functions necessary to help Lockheed develop the technology into an engineering package.
We detail this work as the following three (3) tasks, each with a dedicated Research Assistant (RA).
Part of this work will be to define interfaces to the CM for software modules and to define the set of messages with which the CM will interact with domain agents and the Redux' agent.
A major subtask is to define the protocol of messages to and from domain agents, the CM, and Redux'. A second major subtask is to deliver extensions of Redux sufficient to manage projects and treat process planning in the same way as artifact design and combine the two types of design. A third subtask is to allow the user to hypothesize a change in the schedule and see the results without changing the existing plan. A fourth subtask will be to implement a theory of authority so that each user can only change that part of the schedule and design assigned by the Design Manager. The DM, on the other hand, should be able to change any part of the design. Hypotheticals and levels of authority will require substantial modification of Redux.
The PM will consist of a set of agents, one of which shall be the Redux` agent. This will be used initially with existing systems to provide automatic notification of changes in design tasks and to coordinate them. Other agents will be added to provide the integration of process planning and artifact design and manage project change.
The development of this interface will include the following:
Figure 1: Next-Link NEDL Transactions
Figure 1 illustrates connections between the agent deliverables using some example NEDL transactions. On the left side of the figure are SBD-specific agents. Examples would be geometry or optical CAD tools that have been wrapped with the appropriate ``middleware'' Application Program Interfaces (APIs) to qualify as Next-Link agents. (See the next subsection.)
On the right side are generic Next-Link agents that provide domain-independent services. Communications between agents use NEDL. One example illustrated is the request of the geometry agent for the evaluation of a variable with a continuous domain. This request goes to the Constraint Manager, which routes it to the appropriate constraint solver. The answer returned contains a set of consistent intervals.
Another example illustrated is the notification of the optical and geometry agents by Redux' that they are connected by a constraint violation. This violation may be resolved by the Design Manager that rejects an optical decision, resulting in loss of progress on a task to be performed by the optical agent, as determined by Redux'.
Illustrated also is a request by the Design Manager for the Project Manager to evaluate a hypothetical change to the design. The Project Manager uses Redux' to determine the connections between the artifact design and the project process plan. Resulting effects are conveyed to the Design Manager.
Finally, figure 1 also shows that the MECE Design Manager is capturing and writing design information in the new EDNL language, and using this information to send messages to the other Next-Link agents.
Figure 2: Next-Link Agent Middleware
As illustrated in Figure 2, Next-Link agents delivered will use either KAPI or CORBA as the ``middleware'' for transporting NEDL messages. Every agent participating in the Next-Link framework will have a Next-Link API (NAPI) for sending and receiving NEDL messages. Each agent will also have a KQML API (KAPI) so that it can communicate with other, non-Next-Link agents and when an CORBA API is not available.
Next-Link generic service agents will also have a CORBA API when available. The Redux' agent is an example of a Lisp-based agent for which no CORBA API is yet available. However, it will only be communicating with agents within the Next-Link framework, so this is not problematic.
All software delivered for which a CORBA API is available will be CORBA-compliant. KAPI-wrapped agents will have a CORBA object description enabling the agents to be called as CORBA objects by a suitable ORB. All functions will be available as object methods.
SBD-specific agents with in Next-Link may communicate to other SBD software with ad hoc (non-NEDL) messages via CORBA interfaces.
Figure 3: Next-Link Federation
There are many factors to be considered in scaling. We are proposing an extensive bookkeeping task to be automated. The first factor to consider is that this task needs to be done now and people do it poorly. Whatever difficulties a computer may have, the results can only be better.
Second, there is the issue of experience with the underlying Truth Maintenance System technology. We use a justification-based TMS, not an ATMS. And while the task of labeling a TMS network is in theory NP-hard, large networks in practice always have sufficient locality of connections such that network labeling is a small part of whatever computation task being performed. If everything is represented as conncected to everything, then no system, human or computer, will be of any value.
The most important consideration is proper analysis of the tasks. The proper granularity of design elements must be determined. And the proper degrees of interconnectivity between subsystems must be determined. Given that the latter can be done, the Next-Link framework can use the well-known technique of ``federation'' to handle scaling. Separate Next-Link frameworks, as illustrated in Figure 3, can be constructed and connected by separate Redux' agents in each framework. This figure points out that the Next-Link approach to integration of engineering software is not limited to small scales but is scalable to the degree that any integration technique would be by proper task analysis.
We note that there is a problem, always, with understanding the ramifications of change. We do not propose a general solution to this problem, to which most ``solutions'' do not in fact scale. However, the proposed technology offers a structured framework on which various approaches to ramification prediction may be tried.
[Faltings] Faltings, B., ``Arc-consistency for continuous variables,'' Artificial Intelligence 65, 1994.
[Haroud] Haroud, D. and Faltings, B., ``Global Consistency for Continuous Constraints,'' Lecture notes in Computer Science 874: Priciples and Practice of Constraint Programming, Alan Borning (ed.), Springer Verlag, 1994.
[Park] Park, H., ``Modeling of Collaborative Design Processes for Agent-Assisted Product Design", Dissertation, Center for Design Research, Stanford U., January, 1995.
[Petrie-94] Petrie, C., Cutkosky, M., & Park, H., ``Design Space Navigation as a Collaborative Aid,'' Proc. AI in Design: 3rd Internat. Conf. pp. 611-623, Lausanne, August, 1994.
[Petrie-95] Petrie, C., Webster, T., & Cutkosky, M., ``Using Pareto Optimality to Coordinate Distributed Agents'' Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AIEDAM), to appear.
One of the essential functions of the Redux' agent is that it notices when one design decision is rejected in favor of another and it constructs a design rationale based upon the conditions at the time of the rejection. If a constraint violation is declared and one decision is rejected in order to resolve it, then this is remembered as a reason for a subsequent decision. And the constraint violation is remembered as a reason for the rejection. This follows an implicit model of ``generate and test" for constraint violations. A design rationale can always be produced.
Early experiments with Next-Link have shown that surprising and useful information can be dynamically generated with this approach. Users may receive messages with unanticipated useful advice about how to change the configuration of the current design. Each message may be well-understood in light of the explanation that the Redux' agent sent, but, because of the complexity of the interactions among the designers, the user would have failed to detect the opportunity noticed by Redux'.
In addition to this high level source of technical incompatibility, there are two other general difficulties stemming from the fact that not all CSP solvers have the same functionality. CSP-solving is a hard problem, so various algorithms trade-off completeness for tractability. Most often, a CSP requires a structured network with an enumeration of variables and possible values and then performs a version of arc-consistency.
Arc-consistency does not ensure consistency. Generate and test is still needed. And if an inconsistency is found, there may be insufficient information to backtrack. The approach we are taking is to use a K-consistency algorithm at this point to generate the missing information.
Another difficulty is that some techniques are simply fundamentally different because the solve in different domains. Discrete problem solvers may have enumerated possibilities for a finite number of variables and constraints. Solving cryptograms is the prototypical example of the class of problems for which these techniques are suited. Other systems allow infinite variable domains or to be dynamically expanded. At one extreme are algebraic constraint solvers and temporal logics that solve continuous variables by propagating intervals. One needs such a solver to reduce inequalities, for example. They are also good for continuous scheduling problems. And one often needs different CSPs to solve different parts of the same problem in engineering.
As an example, a task domain agent may send the CM a request to evaluate the domain of a variable and identify good solutions. Or two domain agents may request joint solutions. Or a domain agent may declare that no solutions are good and request backtracking information. Constraints may be added or relaxed. In all cases, Redux' is working with the task domain agents and the CM to capture the design rationale and identify non-intuitive situations that ought to be noticed by some user.
The CM messages include at a minimum:
Project planning with such functionality is limited because it is static. When something changes within a project process, it may be difficult to incrementally revise the plan. First, backtracking is not supported. If one task takes more of a resource than expected and thus conflicts with other tasks, existing tools provide little support for changing the plan to resolve the conflict while changing only the parts of the plan necessary. Similarly, if a person with certain skills is not available at the time planned or if a particular building material does not arrive on schedule, it is difficult to adjust the plan.
Second, it is often the case that subtasks are delegated to different people and machines and yet the subtask relationship is not managed by existing tools. If a subtask becomes invalid because of a higher-level change, this may not be communicated as necessary. If a subtask cannot be performed because of higher-level decisions, the relationships may not be understood.
Third and most important, there is an important interplay between the evolving artifact design and the process plan. As the former changes, because of design and development decisions, the latter may need to change. Traditional project planning technologies cannot take this into account. So it is often the case that the project plan becomes obsolete quickly. This is even more the case when the project is distributed as is the case with many modern projects.
Redux implements a theory of design that integrates dependency-directed backtracking and subtasks. Potentially, this could result in a more dynamic project management tool for applications as diverse as civil engineering to material logistics. The key idea is to treat project planning as a design and to integrate it with the design of the artifact.
However, Redux lacks some necessary concepts. One of the major extensions needed is to add formal notions and dependencies for when a task is ready to begin: all of the prerequisites are in place. Similarly, there is a notion of when a task is complete. At any time, a project manager should be able to see the state of the project with respect to the status of the tasks.
Further extensions needed are to implement notions of time, consumable resources, and commitment. Time is necessary, for example, to predict durations and to schedule tasks. The general notions of constraints and constraint violations in Redux need to be be more specified in the case of consumable resources, such as money, disk space, or people with certain skills in a particular timeframe. When a task has already been performed, or is underway, replanning cannot alter it: it is committed. Other modifications are necessary, such as a stronger notion of authority to assign and reassign tasks to subcontractors.
Extensions needed include as a minimum representations of:
We further propose that this work make use of existing complementary work at the University of Kaiserslautern. Dr. Frank Maurer is supervising three relevant Master's projects. B. Dellen is developing some task extensions to Redux that can be used in this work. Two other planning projects are developing partial and complete orderings of Redux subgoals based on resource and time requirements.
In addition to thus extending the Redux' agent, a new project planning agent should be written that can schedule and revise a project using the new Redux' extensions. This should be a distributed application with some tasks delegated to distributed agents that must all work together to accomplish a project. A suitable domain will be provided. However, the main work is not to build such a planner. This work has been done and does not require research. The research work is to develop the extensions and message protocols so that a project planner/scheduler can work with Redux' and the CM.
The messages will define the inputs and outputs to the PM. They will define the use of constraint solvers in the CM for planning and replanning. And they will define messages to and from Redux' that will allow the schedule to be incrementally changed depending upon changes in the project environment and whether or not tasks were completed as scheduled, both in regard to time and resources.
Thus the Project Manager(PM) proposed is similar to the CM. It will be an ``envelope'' for various project management planners and schedulers. The message protocol will determine the extent to which the constraint solvers in the CM can be used to build or critique the schedule, which is based upon time and resource constraints. Sufficient information must be contained in the messages at some point to allow Redux' to dynamically revise the schedule.
Traditional functionality such as CPM and GANT charts will be available, but will be dynamic and incrementally revisable as the artifact design and the project plan change. The primary work of this task is not to develop such a PM from scratch, but rather to define the interface with the rest of the Next-Link system. We will either find a suitable planner or provide an interface so that a user can try out schedules.
We do not propose to develop any new scheduling algorithms in this task. The hard research is conceptual. How should a PM be able to make use of the CM? What information needs to be passed to Redux', and when, to allow rescheduling? What is the best representation of hypothetical schedules. What is a good user interface? What sorts of project planners could work with Redux' in providing rescheduling information.
The advantage of the EDNL approach is that it can be used in many ways. Different clients may have different capabilities. If the EDNL has, for example, keywords that allow overlays, some clients may be able to handle these much like a Canvas(TM) application, perhaps even making 3D overlays and/or replaying a history and allowing temporal animation. But other simpler clients may only be able to display a compiled gif image. An EDNL also will allow clients run helper applications more easily than is possible with HTML.
We propose to develop the basis of such an EDNL sufficient to enable Redux to be used as an active agent to help the user coordinate his own and others' design decisions. By ``active'', we mean that Redux will unobtrusively watch the users actions and surprise the user with helpful advice every now and then.
The EDNL will have a formal notion of ``decision" that will hopefully correspond with Redux's. This should be relatively easy to implement with EDNL keywords. The primary work will be to alter the MECE user interface to take advantage of the Redux functionality.
Also, a major piece of work, though not conceptually difficult, will be to create wrapper software that translates MECE user actions into KQML message to be sent to Redux' and other Next-Link generic service agents.
An optional task is to make this communication service work like an electronic mail POP server. The MECE software need not be connected to the network all of the time but can rather send and receive messages later than when the work was actually done. This POP-like service will require considerable conceptual design.
Finally, MECE should be extended to take advantage of the project management capabilities proposed here. This would allow a Design Manager (DM), or perhaps DMs at various levels of authority to see a graphic display of the state of the project, to initially plan the project, and to incrementally revise the project as needed, especially based on Redux messages notifying the user of opportunities to improve the design, the process plan, or both.