A-DESIGN - AGENT BASED ADAPTIVE CONCEPTUAL DESIGN
INTRODUCTION | ITERATIVE SEARCH PROCESS | MULTIOBJECT DESIGN SELECTION | MULTI AGENT ARCHITECTURE | FUNCTIONAL REPRESENTATION | A DESIGN AS SEARCH STRATEGY | TEST RESULTS | DISCUSSION AND CONCLUDING REMARKS
A-DESIGN AS SEARCH STRATEGY
The following two test examples explore the effectiveness of the A-Design theory as a computational search tool. They were created to test individual sections of the theory and are presented here to illustrate the capabilities of the methodology. The first demonstrates the operation of the multi-objective design selection and interaction of agent subsystems, while the second challenges A-Design with a numerical optimization problem. In each of these examples, the design representation and agents are quite simple. After this exploration of the operation of the general components of A-Design, a richer representation and set of agents is introduced in Section 5 for the complex conceptual design problem of electro-mechanical configuration design.
1.1 MANHATTAN TRANSFER
This example presents a problem for which it is relatively easy to find solutions, but difficult to find solutions that maximize the satisfaction of the traveler’s preference. The object of the Manhattan Transfer problem is to get from one location to another in a grid-based city in the minimum amount of time, cost, and effort. A user specifies the start and end location of a trip as the initial specification to the algorithm. It is the algorithm’s duty to find solutions that connect the start and end locations via various transportation media. A simulated two-dimensional grid of squares represents city blocks while the transportation devices consist of bike, walk, run, bus, taxi, and subway; each having different values for the cost, time, and effort required. The problem specification requires A-Design to create alternatives using combinations of the 6 transportation devices in order to best satisfy the user’s weighted criteria of minimizing cost, time, and effort.
The process starts as in Figure 2 with the maker-agents contributing partial travel paths along the way to the creation of complete trips. Rather than each agent solving the complete problem from start to end, the maker-agents subgoal on shorter trips that combine to make a complete solution. Therefore all design states are the result of the combined effort of several maker-agents. These maker-agents differ in which transportation device they add to a trip and how they handle constraints in the system such as bus and subway stops, and maximum distances one can walk or run. After maker-agents complete designs, the designs are evaluated on their cost, time, and effort, and solutions are sorted into pareto, good, and poor populations. Next, modification-agents remove elements from solutions that are believed to be preventing designs from reaching optimal states and return the fragmented designs back to the maker-agents for reconstruction. After modification, another iteration ensues until the process is finished and returns to the user a solution represented as a list of transportation devices with their start and stop locations making up the complete travel plan.
The Manhattan Transfer results are generated by specifying the beginning (0, 0) and end (20, 20) locations as well as the relative importance of each objective. At the end of the process A-Design returns several solutions that best meet the user preference. For example, if the user feels that minimizing cost is more important than minimizing time or effort, a solution such as the one shown in Figure 4 is suggested. This solution was generated for a user whose preference for cost is five times more important than time and two times more important than effort. The design was found in 62 iterations with a maximum design population of 160. In addition, the user is free to change preference throughout the process allowing the system to adapt appropriately. By examining the results produced the user can adjust the preference weighting to achieve the desired trip. In this example, user preference was changed midway through the process to prefer minimizing time twice as much as effort and 5 times as much as cost thus producing the result of “take taxi from start to finish? By using the population of designs created under the old preference, which includes a variety of designs, the process is easily adapted to this new preference. As a result, the algorithm took only 11 iterations to converge, thus illustrating the power of the recessive traits stored in the pareto set. It was determined through a separate experiment that the complete space of uniquely evaluatable design states numbers approximately 1.2 million and that of these, only 99 are pareto optimal. In comparison, A-Design found 40 pareto points of the 99 while searching only 0.6% (approximately 7000 design states) of the design space.
Although the Manhattan Transfer example deals with a highly abstracted situation, it illustrates that agents with different characteristics are able to work together to find optimal design configurations and their interaction produces a flexibility in adapting to changes. Alone, the agents consider minimizing only single objectives. For example, low-cost designs are usually created by agents that prefer low-cost devices. Through the collaboration of different agent types, solutions are constructed that exemplify the preferences suggested by the user. The combination of agents that prefer low-cost devices with agents that prefer low-effort devices will ideally lead to designs that are both low in cost and low in effort. In the example, the initial user preference was for low-cost designs, however when the preference changed to emphasize quick trips, A-Design was able accommodate this alteration and switch focus to agents with a preference for quick designs. The example also demonstrates the algorithm’s effectiveness in advancing the pareto optimal front through the various iterations. Early iterations produce a set of alternatives that through modification lead to better states which in turn add new solutions to the pareto surface and remove previous ones that are shown to be suboptimal.
In addition to A-Design’s ability to adapt to changes in user preference is the need for A-Design to optimize the various objectives specified by the user. This example, therefore, tests the optimizing power of A-Design apart from its use as a conceptual design generation tool. In its final form, A-Design creates designs to best meet the objectives and constraints specified by a user and is thus driven toward optimally directed configurations.
1.2 NUMERICAL OPTIMIZATION
This example sets up two numerical functions to be optimized in order to maintain a multi-objective problem. The two functions shown in Figure 5, are expressed by
where the minimum is -234.6 and is found at (x = -1.57, y = -1.57).
These functions are both highly multi-modal and therefore difficult to solve by traditional methods. A-Design was compared with a robust SQP algorithm (Lawrence, et al., 1993) in finding an optimum for a weighted sum of the two objectives. Both systems were first tested by weighting f1 ten to one over f2, and then tested again with a weighting of f2 ten to one over f1 using the results of the first run as the initial specifications for the second run. The 10:1 and 1:10 preferences are used to establish quite different optimal points for the lumped objective functions. Agents within this problem are simple functions that increase or decrease parameters within the equations to reduce objective values or avoid local minima.
A single run of A-Design proved to be a time-consuming process, partly due to the number of design state evaluations and partly due to agent and design management. Although SQP found the optimal solution quicker for the 10:1 weighting, it successfully found the global minimum only one out of seven times. The A-Design algorithm, due to its agent-based search and storing of design alternatives, found the solution in every run with a population size of 100 and an average of 88 iterations. When the weightings changed, A-Design only needed to perform a single iteration to arrive at the new optimum, while SQP had to be rerun 13 times before finding the new optimum. By retaining the pareto optimal set from the first run, the A-Design algorithm quickly adapts to changes in weighting of the two objectives. Certainly, SQP is a more efficient optimization strategy if it starts in the neighborhood of the optimum. However, A-Design is, in general, more robust in its ability to find the optimum and the time required in arriving at pareto optimal solutions for the first user preference results in a large savings when the process is reinitiated with different weights.
The two examples discussed above demonstrate the versatility of the A-Design methodology. Both examples illustrate the methodology’s potential outside the intended use as a conceptual design tool. These examples show that A-Design, through its unique design selection scheme of preserving the pareto front and iterative-based agent operations, can successfully produce results for a wide variety of problems.