Towards A Knowledge Based Cable Router for Aerospace Vehicles

Towards A Knowledge Based Cable Router for

Aerospace Vehicles

The 2006 International Conference on Information & Knowledge Engineering Christian Van der Velden1*, Cees Bil1, Xinghuo Yu2, Adrian Smith3

1School of Aerospace Mechanical and Manufacturing Engineering,

RMIT University

Melbourne, Victoria, AUSTRALIA

S2108846@298f49240722192e4536f699.au

cees.bil@298f49240722192e4536f699.au

2School of Electrical and Computer Engineering,

RMIT University

Melbourne, Victoria, AUSTRALIA

x.yu@298f49240722192e4536f699.au

3GKN Aerospace Engineering Services Pty Ltd,

Brisbane, Queensland, AUSTRALIA

adrian.smith@298f49240722192e4536f699

Abstract

The design of electrical wiring and hydraulic/pneumatic piping routes in aircraft is a long and repetitive process which is largely done by hand. Presented in this paper is progress in the development of a knowledge based routing system which automates much of the routing process using intelligent algorithms and interchangeable design rules. The system reads three dimensional CAD models to be navigated and source and target locations, and outputs wire/pipe paths.

Keywords: knowledge based engineering, intelligent algorithm, routing, CAD, Finite Element, Voxel

1 Introduction

The management and utilisation of data is of great importance within the engineering field. Knowledge Based Engineering (KBE) is a set of methodologies for enhancing engineering design processes through effective knowledge management. KBE systems are software applications which collect, store and utilise engineering rules and knowledge and are used for design automation, verification, and integration of design and production knowledge. Use of these practices facilitates a smooth transition between product lifecycle phases.

Electrical wiring looms in aircraft typically consist of thousands of cables and are usually routed by hand using Computer Aided Design (CAD) workstations with engineers using personal knowledge and experience of how to route cables through the structure. There are numerous regulatory and functional design rules which must be satisfied (such as bend radii, electromagnetic sensitivities, placement of support brackets, protection against corrosion and abrasion, cable bundling, intersections between cables, divergence of cable bundles, etc.). The routing process is highly repetitive and design outputs can vary significantly between engineers. Electrical wiring design often proceeds in parallel with principle structural design. The iterative nature of the total design process is such that structural changes are prone to occur requiring time consuming rework for any electrical cabling affected. In a similar way, hydraulic and pneumatic pipes in aircraft are manually routed and are governed by different set of design rules. The repetitive, rule-governed nature of the routing process makes it a prime candidate for application to a knowledge based system.

Fig. 1. Example of routed electrical loom

This paper describes current progress in the development of a knowledge based system for three-dimensional routing in aerospace vehicles with applications including electrical wiring and hydraulic/pneumatic piping design. The concept of the software is to read 3D CAD geometry with source and target terminals and output wire/pipe geometry and other information required to describe the system path. Section two of the paper discusses the general routing problem and the approach used for solving cases. The third section gives a description of the path finding algorithm used. Section four discusses input geometry issues including use of finite element and volume graphics for representing CAD models. Following this, a description of the process flow of the knowledge based system and concluding remarks are given.

2 Routing Problem and Process

The connection of multiple terminals within a set space with obstacles is a commonly encountered problem in nume rous fields ranging from electronics (for example printed circuit boards), microelectronics (for example Very Large Scale Integrated circuits), information flow in computer networks (for example data packets over the internet), navigation systems (for exam ple GPS) and artificial intelligence (for example robot path planning and computer game navigation).

Practices in VLSI routing automation provides a good starting point for addressing the problem of electrical loom and pipe design in aerospace vehicles. Computer microprocessors consist of many million logic components which must be interconnected within a very small space using very

fine wires. The VLSI routing problem is considered NP-complete commonly requiring the use of powerful heuristics which can generally find near optimal solutions. In the case of electrical looms in aircraft, the number of connecting wires to be routed, or nets, is several orders of magnitude less than computer chips therefore routing algorithm run time would be expected to be significantly less.

In general once the physical component placement for a system has been defined and the routing requirements given (usually in the form of a netlist), the routing process consists of four main steps [2]:

? Definition of regions: problem is divided

into smaller routing problems.

? Global routing: planning phase which

assesses and prioritises nets to maximize completion rate (proportion of solvable nets) and minimize total path length, especially for critical nets, to reduce delay. ? Ordering regions: determines order in

which regions are routed such that congestion will be avoided.

? Detailed routing: determines the exact path

taken by wires including layers, connecting vias.

There are numerous algorithms for a variety of routing applications in different stages of the routing process as well as for specialised applications. Fig. 2, modified from [12], shows a family of routing algorithm types and their use in different phases in the routing process. The list is by no means exhaustive, but covers several of the common routers: which are maze, channel/switchbox, and line search/probe algorithms.

Fig. 2. Family of routing algorithms. Taken from [12].

3 Routing Algorithm

In its basic form, the algorithm used by the system to determine the path is based on the classic breadth-first, grid-based maze algorithm or Lee’s a lgorithm [6]. Lee’s maze router always returns the shortest path for a single net in a given search space with

obstacles. The algorithm functions by propagating a wave from the source and/or target terminals over a grided search area and assigns a value to each node depending on its distance from the source or target. A backtracking phase then determines the shortest path between the two terminals (see Fig. 3).

Fig. 3. Exam ple of maze routing. (Left) wave propagation from source only. (Right) wave propagation from

source and target

The basic form of the maze algorithm has numerous limitations of which the main problem is sensitivity to the order in which nets are routed. Paths from routed nets form obstacles for subsequent nets and in some cases can prevent nets from being completed. In cases where this is encountered, a rip-up-and-reroute procedure can be used which removes routed nets and retries in a different order. In addition to this, the algorithm is inefficient when routing more than two terminals in a single net. In the case of multi-terminal nets, the connection between two terminals is found, then the partially routed net is treated as the source for remai ning terminals. Also, the algorithm is inefficient when routing terminals in large empty spaces.

To address shortcomings of the basic maze algorithm, a large number of alternative path finders have been developed based on Lee’s basic maze approach and use d in numerous applications. One example is the A* (A star) algorithm which is used extensively in computer game navigation and uses a “best-first” search technique to determine path steps (Fig. 4 left) [8]. A score is given for each node (F) based on minimum distance to target (H) and distance from source (G). Nodes with lower scores favoured. Another example is Hadlock’s algorithm which uses a “greedy” search technique and adds penalties for every deviation away from the target (Fig. 4 right) [12].

Fig. 4. Example of extensions to the basic maze algorithm.

(Left) A* algorithm: G = distance from source, H = distance to target, F = path score (G + H). [8] (Right) Hadlock’s algorithm penalty for nodes deviating from ideal (no obstacle) path. [12]

The algorithm under development uses object -based programming principles and implements intelligent search techniques such as best-first and greedy searches. As far as possible, the algorithm uses intuitive, plain English terminology in its implementation. The algorithm will access a knowledge base of electrical design rules collected from regulatory documents such as military specifications (for example MIL-W-5088L: Wiring, Aerospace Vehicles) and civil airworthiness requirements. This knowledge base will be

interchangeable allowing rule sets for different routing applications to be plugged in. Whereas most VLSI routing algorithms are based on a multilayered 2D approach, algorithm used in this system can solve full 3D mazes of any dimension. Multiple nets can be routed in the same search space. Multi-terminal nets can also be routed by routing the path between two terminals first and then connecting additional terminals to the original path.

Fig. 5. 3D path finding demonstration applet. Dark gray: start location, Gray: finish location, Light

gray: path, Black: obstacle

A screen capture of a 3D demonstration applet is given in Fig. 5. To visualise the results in 3D, the applet writes a Finite Element input file for NASTRAN which defines the path in nodes connected by 1D PROTEL elements, and obstacles given as solid 3D elements with the solution space bounded by a cube comprised of PROTEL elements. An example of the finite element visualization of the problem shown in Fig. 5, is given in Fig. 6. At this stage no optimisation of the algorithm has been attempted thus the efficiency is limited to O(d3). However, for the applet shown in figure 5, the main cost in terms of processing time is the visualization using the standard windows graphics. The visualization will be improved with the use of OpenGL in the near future.

Fig. 6. 3D representation of search space, path and obstacles using Finite Element software

4 Geometry Factors

To apply a grid-based algorithm to the routing problem, the 3D model of surrounding structure and obstacles with source and target positions is to be discretised. Currently two methods of geometry preparation are under consideration which use Finite Element (FE) and Voxel modelling techniques.

4.1 Finite Element

The first method uses a finite element (FE) modelling approach which is common procedure in the engineering process of analysing the response of structures to loading. For this method, empty space in the model will be meshed using solid el ements (for example CHEXA elements, Fig. 7), and this mesh searched for a valid path between given source and target. Property cards are used to identify between structural mesh and the search space mesh. The advantage of this method is that geometry importing and meshing is standard practice in the engineering design process, and existing knowledge and sof tware can be utilised. Also the mesh fineness can be easily varied depending on accuracy required for net path.

Fig. 7. FE solid mesh

The searching process would proceed as shown in Fig. 8 and would begin by searching for and selecting the starting node and then querying the element list for attached elements. The algorithm would then select the “best” a ttached element based on a rule module and the direction of the target. From this element, attached nodes can be determined and the best node selected based on similar rules. This process of s electing nodes then attached elements would continue until the target is found and all conditions satisfied.

One of the disadvantages of this method is irregular mesh shapes and inconsistency of element and node ID labeling (i.e. element no. 1 may not necessarily be attached to element no. 2, etc.), and reflecting changes in the mesh.

Currently the maze finding application can read a simple FE mesh with source and target nodes (defined using entity sets), solve the routing problem and export back to an FE format.

Fig. 8. Searching process using FE methods for

geometry discretisation

4.2 Voxels

3D models in virtual environments such as CAD/CAM applications and computer games are traditionally represented using surface graphics which are composed of polygon meshes (usually triangles) over hollow shells. For high quality visualisation of models, a large number of polygons is required. For each polygon complex computations are performed to determine shading requiring high end computer graphics hardware for display.

Volume graphics is an emerging technology in 3D model represent ation which uses stacks of 3D cube elements called voxels (or volume pixels) which are analogous to pixels in 2D images [11]. Voxels are defined by a number of characteristics including size, address (in x, y and z coordinates), state (on or off), colour, density, etc. (See Fig. 8 taken from [5] a provider of volume graphics software). A voxel rendering engine assumes all voxels are facing the “camera” at all times as the model is rotated, thus the memory requirement can be reduced to a single position and colour for each element and global voxel size. Whereas surface graphics require complex computations to determine shading, volume graphics can be displayed without use of high end 3D acceleration hardware.

The main advantage of this method lies in ease of implementation. Whereas surfaces modelled in traditional CAD software use complex relationships, volume graphic representation uses a fixed x, y, z integer-based address for each element allowing a grid based alg orithm (such as those discussed in section 3) to be directly applied to the problem. The searching process would proceed as shown in the flowchart in Fig. 10.

Fig. 9. Voxels represented in 3D space.

The disadvantage of this method is the availability of voxel software. Some open source voxel engine software is available freely on the internet, however the power of these applications is limited, requiring expensive commercial software (such as that used in laser scanning of three dimensional models). Many commercial software packages include conversion utilities from common CAD model formats (such as IGES, DXF, STEP) to voxelised representation.

Fig. 10. Searching process using voxel methods for

geometry discretisation.

5 Knowledge Based Router The knowledge based routing system comprises a number of steps which are as follows. Firstly, physical structure is designed and modelled using CAD software by structural engineers. Electrical or piping requirements are defined in terms of start and finish locations and other relevant characteristics such as category of load etc., and are given in the form of a netlist. The 3D model is then exported from the CAD package using a neutral file format such as IGES or STEP. The CAD model is converted to a discrete format suitable for applying a grid based search algorithm using either finite element or voxel techniques as discussed in section 4. The discrete data set is then extracted and fed into the maze algorithm which determines the paths for multiple nets given constraints stored in the knowledge module. This module can be interchanged for different routing applications, not necessarily limited to aircraft (for example a rule set for air conditioning ducts in buildings could be developed). After execution of the routing algorithm, the output path (defined in FE or voxel elements) is converted to wiref rame geometry which is imported into a CAD package and detail added according to the knowledge base consulted in the process. These steps are summarised in the flowchart in Fig. 11.

Fig. 11. Knowledge based router process flow.

6 Conclusion

This paper has briefly covered the concept of a knowledge based router currently in development which will have applications in electrical wiring and hydraulic/pneumatic pipe design. The system itself consists of a number of main elements including: a knowledge base for storing routing rules and constraints, a method of discretising geometry using either finite element or voxel modelling techniques, and an intelligent path finding algorithm to navigate the structure and return a valid path for the wire/pipe.

Ref erences

[1]Arnold, M. H., and Scott, W. S. “An Interactive

Maze Router with Hints”. Lawrence Liver-more National Laboratory, University of California, 1988.

[2]Groeneveld, P. “Electronic Design Automation,

Part 1”. Technische Universiteit Eindhoven, The Netherl ands, 2005.

[3]Guruswamyl, M., and Wong, D. F. “A General

Multi-layer Area Router”. The University of Texas at Austin, Department of Electrical a nd Computer Engineering, 1991.

[4]Joobbani, R., Siewiorek D. P. “WEAVER: A

Knowledge-Based Routing Expert”. Department of Electrical and Computer Engineering, Carnegie-Mellon University, 1985.

[5]Kaas, E.“The NGRAIN Technology Difference

Explained A Whitepaper For Technical Evaluators Of Visualization And Simulation Technologies”. NGRAIN Corporation.

Vancouver, Canada.

[6]Kang, S.-S., Myung, S. and Han, S.-H. “A

Design Expert System for Auto-Routing of Ship Pipes”. Journal of Ship Production, 1999. [7]Lee, C. Y. “An Algorithm for Path Connections

and its Applications”. IRE Transactions on Electronic Computers vol. EC-10, no. 2, 1961.

[8]Lester, P. “A* Pathfinding for Beginners”.

Almanac of Policy Issues website, 2005. URL: 298f49240722192e4536f699/games/aStarTuto

rial.htm

[9]Lunow, R. E. “A Channelless, Multilayer

Router”. Lawrence Livamore National Laboratory, California, 1988.

[10]Stevenson, A. “Voxels And Volumetric

Representation”. The University of British Columbia, Vancouver, Canada, 1996.

[11]Tehranipoor, M. “CAD Algorithms – Routing”.

Department of Computer Science and Electrical Engineering, University of Maryland, Baltimore County, 2005.

[12]Vakil, D., Zargham, M. R. “An Expert System

for Channel Routing”. Computer Science Department, Southern Illinois University, 1988.

[13]Van der Velden, C., Bil, C., Yu, X. Smith, A.

“Mathematical Techniques Applied to Knowledge Based Engineering Design Systems”. Engineering Mathematics and Applications Conference, Melbourne, Australia, 2005.

[14]Yoshimura, T., and Kuh, E., S. “Efficient

Algorithms for Channel Routing”. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1982.

本文来源：https://www.bwwdw.com/article/fyle.html