Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-06T09:16:38.139Z Has data issue: false hasContentIssue false
  • English
  • Français

Automobile transmission design as a constraint satisfaction problem: modelling the kinematic level

Published online by Cambridge University Press:  27 February 2009

Bernard A. Nadel  and
Jiang Lin
Bernard A. Nadel
Affiliation:
Computer Science Department, Wayne State University, Detroit, MI 48202, U.S.A.
Jiang Lin
Affiliation:
Computer Science Department, Wayne State University, Detroit, MI 48202, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper describes our preliminary results in applying constraint satisfaction techniques in a system we call TRANS-FORM for designing automatic automobile power transmissions. The work is being conducted in collaboration with the Ford Motor Company Advanced Transmission Design Department in Livonia, Michigan. Our current focus is on the design of the mechanical subsystem, but we anticipate extending this later to the electrical and hydraulic subsystems also. For simplicity, in the initial work reported here we restrict ourselves to the relatively well-explored class of transmissions having four forward speeds and one reverse speed, built from two planetary gearsets, cross-connected by two permanent links. Moreover, we pursue design of such transmissions only at the ‘kinematic level’. These two restrictions correspond to limiting respectively the breadth (generality) and the depth (detail or granularity) of the search space employed. We find that, at least for the restricted version of the problem pursued here, transmission design is an application very naturally formulated as a constraint satisfaction problem. Our present problem requires only 10 variables, with an average of about seven values each, and 43 constraints—making it similar in difficulty to about the 10-queens problem. So far, two of the classic transmissions, known as Axod and HydraMatic, have been rediscovered (at the kinematic level) by our program. Preliminary results also indicate that the constraint satisfaction framework will continue to remain adequate and natural even when the search space is allowed to be much broader and deeper. We expect that searches of such expanded spaces will soon lead to the discovery of totally new transmissions.

Type
Research Article
Information
AI EDAM , Volume 5 , Issue 3 , August 1991 , pp. 137 - 171
Copyright
Copyright © Cambridge University Press 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allen, J. F., 1983. Maintaining knowledge about temporal intervals Communications ACM, 26 (11), 832–843.CrossRefGoogle Scholar
Barrow, H. G. and Tenenbaum, J. M., 1976. MSYS: A system for reasoning about scenes. Technical Note 121, Artificial Intelligence Center, Stanford Research Institute.Google Scholar
Brown, C. and Purdom, P. W. Jr 1981. An average time analysis of backtracking. SIAM Journal of Computers 10, (3), 583–593.CrossRefGoogle Scholar
Cohen, P. R. and Feigenbaum, E. A. eds. 1986. The Handbook of Artificial Intelligence, Vol. 3. Reading, MA: Addison-Wesley.Google Scholar
Davis, L. S. and Rosenfeld, A. 1981. Cooperating processes for low-level vision: a survey. Artificial Intelligence, 17, 245–263.CrossRefGoogle Scholar
Dechter, R. 1987. A constraint-network approach to truth-maintenance. Tech. Report R-870009, Cognitive Systems Lab., Computer Science Dept., U.C.L.A., Los Angeles.Google Scholar
Dechter, A. and, Dechter, R., 1987. Minimal constraint graphs. Proceedings of the National Conference on Artificial Intelligence (AAAI-87), Seattle, Washington.Google Scholar
Dechter, R. and Pearl, J., 1988. Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence, 34, 1–38. Also in Search in Artificial Intelligence, ed. by Kanal, L. and Kumar, V. pp. 370–425, 1988, New York: Springer-Verlag.CrossRefGoogle Scholar
DeKleer, J. 1986. An assumption-based TMS. Artificial Intelligence, 28, 127–162.CrossRefGoogle Scholar
Doyle, J. 1979. A truth maintenance system. Artificial Intelligence, 12, 231–272.CrossRefGoogle Scholar
Eastman, C. 1972. Preliminary report on a system for general space planning. Communications ACM, 15, 76–87.CrossRefGoogle Scholar
Ellinger, H. E. 1983. Automechanics, 3rd ed. Englewood Cliffs, NJ: Prentice Hall.Google Scholar
Fikes, R. E. 1970. REF-ARF: A system for solving problems stated as procedures. Artificial Intelligence, 1, 27–120.CrossRefGoogle Scholar
Ford Motor Co. 1985. AXOD Automatic Overdrive Transaxle—Operation and Diagnosis. Ford Parts and Service Division, Training and Publications Dept., order no. 1701–205.Google Scholar
Fowler, G., Haralick, R., Gray, F. G., Feustel, C. and Grinstead, C. 1983. Efficient graph automorphism by vertex partitioning. Artificial Intelligence, 21, 245–269. Also in book: Search and Heuristics (1983) Amsterdam: North-Holland.CrossRefGoogle Scholar
Frayman, F. and Mittal, S. 1987. Cossack: A constraints-based expert system for configuration tasks. Knowledge-based Expert Systems in Engineering: Planning and Design, ed. by Sriram, D. and Adey, R. A.Computational Mechanics Publications, 143–166.Google Scholar
Freuder, E. C. 1978. Synthesizing constraint expressions, Communications of the ACM, 21, 958–966.CrossRefGoogle Scholar
Freuder, E. C. 1982. A sufficient condition for backtrack-free search. JACM, 29 (1) 24–32.CrossRefGoogle Scholar
Freuder, E. C. 1989. Partial constraint satisfaction. Proceedings Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), Detroit, Michigan, 278–283.Google Scholar
Gaschnig, J. 1974. A constraint satisfaction method for interference making. Proceedings of the 12th Annual Allerton Conference on Circuit System Theory. University of Illinois, 866–874.Google Scholar
Gaschnig, J. 1977. A general Backtracking algorithm that eliminates most redundant tests. Proceedings of the 5th International Joint Conference on Artificial Intelligence, Cambridge, MA.Google Scholar
Gaschnig, J. 1978. Experimental case studies of Backtrack vs. Waltz-type vs. new algorithms for satisficing assignment problems. Proceedings of the 2nd Biennial Conference Canadian Society for Computational Study of Intelligence, Toronto, Ontario.Google Scholar
Gaschnig, J. 1979. Performance measurement and analysis of certain search algorithms. Department of Computer Science, Carnegie-Mellon University. Ph. D. dissertation.Google Scholar
Hadland, T. 1987. The Sturmey-Archer Story. London: Pinkerton.Google Scholar
Haralick, R. M., Davis, L. S. and Rosenfeld, A. 1978. Reduction operations for constraint satisfaction. Information Sciences, 14, 199–219.CrossRefGoogle Scholar
Haralick, R. M. and Shapiro, L. G. 1979. The consistent labeling problem: part I. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-1 (2), 173–184.CrossRefGoogle Scholar
Haralick, R. M. and Elliot, G. L. 1980. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14, 263–313.CrossRefGoogle Scholar
Haralick, R. M. and Shapiro, L. G. 1980. The consistent labeling problem: part II. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-2 (3), 193–203.CrossRefGoogle Scholar
Heldt, P. M. 1955. Torque Converters or Transmissions, 5th ed. Philadelphia: Chilton.Google Scholar
Husselbee, W. L. 1986. Automatic Transmissions: Fundamentals and Service, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Jones, E. and Route, W. D. 1963. Design considerations in gear noise control. In Noise Control in Automobile Helical Gears. American Gear Manufacturers Association (AGMA), 299.02.Google Scholar
Jones, E. L. 1988. Transmission gear design for strength and surface durability. In Design Practices—Passenger Car Automatic Transmissions, revised 2nd ed. Advances in Engineering, Vol. 5, Society of Automotive Engineers, PA.Google Scholar
Juvinall, R. C. 1983. Fundamentals of Machine Component Design. New York: Wiley.Google Scholar
Kelly, O. K. 1959. The design of planetary gear trains. Society of Automotive Engineers Annual (SAE) Meeting, Detroit A reduced version appears in Design Practices—Passenger Car Automatic Transmissions, revised 2nd ed. Advances in Engineering, Vol. 5, Soc. of Automotive Engineers, PA, 1988.Google Scholar
Lauriere, J. 1978. A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10, 29–127.CrossRefGoogle Scholar
Lynwander, P. 1983. Gear Drive Systems: Design and Application. New York: Marcel Dekker.Google Scholar
Mackworth, A. K. 1977 a. Consistency in networks of relations. Artificial Intelligence, 8, 99–118.CrossRefGoogle Scholar
Mackworth, A. K. 1977 b. On reading sketch maps. Proc. 5th International Joint Conference on Artificial Intelligence, pp. 598–606. Cambridge, MA.Google Scholar
Mackworth, A. K. and Freuder, E. C. 1985. The complexity of some polynomial network consistency algorithms for constraint satisfaction. Artificial Intelligence, 25, 65–74.CrossRefGoogle Scholar
Mackworth, A. K. 1987. Constraint satisfaction. In Encyclopedia of Artificial Intelligence, ed. Shapiro, S. Vol. 1. New York: John Wiley.Google Scholar
McGregor, J. J. 1979. Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. Information Sciences, 19, 229–250.CrossRefGoogle Scholar
Mohr, R. and Henderson, T. C. 1986. Arc and path consistency revisited. Artificial Intelligence, 28, 225–233.CrossRefGoogle Scholar
Montanari, U. 1974. Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7, 95–132.CrossRefGoogle Scholar
Müller, H. W. 1982. Epicyclic Drive Trains—Analysis, Synthesis and Applications. Detroit, MI: Wayne State University Press.Google Scholar
Nadel, B. A. 1986. The consistent labeling problem and its algorithms: Towards exact-case complexities and theory-based heuristics, Computer Science Dept., Rutgers University, New Brunswick. N. J., Ph. D. dissertation.Google Scholar
Nadel, B. A. 1988. Precision complexity analysis: a case study using insertion sort. In review, available as technical report CSC-88–008, Department Computer Science, Wayne State University, Detroit, Michigan.Google Scholar
Nadel, B. A. 1989. Constraint satisfaction algorithms. Computational Intelligence. 5 (4), 188–224. A preliminary version appeared as Tree search and arc consistency in constraint satisfaction algorithms. In Search in Artificial Intelligence, ed. by Kanal, L. and Kumar, V. New York: Springer-Verlag, 1988.CrossRefGoogle Scholar
Nadel, B. A. 1990 a. Representation selection for constraint satisfaction: a case study using n–queens. IEEE Expert, 5 (3).CrossRefGoogle Scholar
Nadel, B. A. 1990 b. The complexity of constraint satisfaction in Prolog. Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, MA, pp. 33–39. An expanded version is available as technical report CSC-89–004, 1989, Dept. Computer Science, Wayne State University, Detroit, Michigan.Google Scholar
Nadel, B. A. 1990 c. Some applications of the constraint satisfaction problem, in review. Available as technical report CSC-90–008, Dept. Computer Science, Wayne State University, Detroit, Michigan. Also in Proceedings of the Workshop on Constraint Directed Reasoning, and in the booklet for the tutorial Constraint Reasoning: Theory and Applications by Mittal, S. and Nadel, B. National Conference on Artificial Intelligence (AAAI-90), Boston, MA.Google Scholar
Nadel, B. A. 1991 a. The complexity of backtracking and forward checking: search-order and instance specific results. In review, available from author upon request.Google Scholar
Nadel, B. A. 1991 b. Automobile transmission design as a constraint satisfaction problem: modeling the gear level. A preliminary version is available from the author.CrossRefGoogle Scholar
Nadel, B. A. 1991 c. Automobile transmission design as a constraint satisfaction problem: modeling the topological level. A preliminary version is available from the author.CrossRefGoogle Scholar
Nadel, B. A. and Lin, J. 1991 a. Automobile transmission design as a constraint satisfaction problem: First results. Proceedings 7th IEEE Conference on Artificial Intelligence Applications, Miami Beach, FL, pp. 248–256. Also reprinted in Artificial Intelligence in Engineering Design, ed. by Tong, C. and Sriram, D. Reading, MA: Addison-Wesley, 1992 (to appear).Google Scholar
Nadel, B. A. and Lin, J. 1991 b. Automobile transmission design: a constraint satisfaction formulation and Prolog implementation. In review, available from authors upon request. A preliminary version appeared in Proceedings of a Workshop on Artificial Intelligece in Design (UCAI-91), Sydney, Australia, 1991, pp. 207–226.Google Scholar
Navinchandra, D. and Marks, D. H. 1987 a. Layout planning as a consistent labeling optimization problem. Fourth International Symposium on Robotics and AI in Construction, Haifa, Israel.Google Scholar
Navinchandra, D. and Marks, D. H. 1987 b. Design exploration through constraint relaxation. In Expert Systems in Computer-Aided Design, ed. by Gero, J. pp. 481–509. Amsterdam: Elsevier.Google Scholar
Navinchandra, D. 1991. Exploration and Innovation in Design: Towards a Computational Model. New York: Springer-Verlag.CrossRefGoogle Scholar
Nudel, B. A. 1982. Consistent labeling problems and their algorithms. Proceedings of the National Conference on Artificial Intelligence (AAAI-82), Pittsburgh, PA, pp. 128–132.Google Scholar
Nudel, B. A. 1983 a. Consistent-labeling problems and their algorithms: expected-complexities and theory-based heuristics. Artificial Intelligence 21, 135–178. Also in Search and Heuristics ed. by Pearl, J. Amsterdam: North Holland, 1983.CrossRefGoogle Scholar
Nudel, B. A. 1983 b. Solving the general consistent labeling (or constraint satisfaction) problem: Two algorithms and their expected complexities. Proceedings of the National Conference on Artificial Intelligence (AAAI-83), Washington D.C., pp. 292–296.Google Scholar
Purdom, P. W. Jr 1982. Evaluating search methods analytically, Proceedings of the National Conference on Artificial Intelligence (AAAI-82), Pittsburgh, PA, pp. 124–127.Google Scholar
Purdom, P. W. Jr 1983. Search rearrangement backtracking and polynomial average time. Artificial Intelligence, 21, 117–133.CrossRefGoogle Scholar
Rit, J. 1986. Propagating temporal constraints for scheduling. Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86), Philadelphia, PA.Google Scholar
Rosenfeld, A., Hummel, R. A. and Zucker, S. W. 1976. Scene labeling by relaxation operations. IEEE Transactions on Systems, Man and Cybernetics, SMC-6 (6), 420–433.CrossRefGoogle Scholar
Route, W. D. 1988. Gear design for noise reduction. In Design Practices-Passenger Car Automatic Transmissions, Advances in Engineering, Vol. 5, revised 2nd ed, Society of Automotive Engineers, PA.Google Scholar
Shanahan, M. and Southwick, R. 1989. Search, Inference and Dependencies in Artificial Intelligence. Chichester: Ellis Horwood.Google Scholar
Shapiro, L. G. and Haralick, R. M. 1981. Structural descriptions and inexact matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-3 (5), 504–519.CrossRefGoogle Scholar
Smith, B. and Kelleher, G. eds 1988. Reason Maintenance Systems and their Applications. Chichester: Ellis Horwood.Google Scholar
Stefik, M. 1981. Planning with constraints (MOLGEN: Part I). Artificial Intelligence, 16, 111–140.CrossRefGoogle Scholar
Tsang, P. 1987. The consistent labeling problem in temporal reasoning. Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI-87), Seattle, Washington.Google Scholar
Ullman, J. R. 1976. An algorithm for subgraph isomorphism. JACM, 23, 31–42.CrossRefGoogle Scholar
Ullman, S. 1979. Relaxation and constrained optimization by local processes. Computer Graphics and Image Processing, 10, 115–125.CrossRefGoogle Scholar
Van Hentenryck, P. and Dincbas, M. 1986. Domains in logic programming. Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86), Philadelphia, Pennsylvania.Google Scholar
Van Hentenryck, P. 1989. Constraint Satisfaction in Logic Programming. Cambridge, MA: MIT Press.Google Scholar
Waltz, D. 1975. Understanding line drawings of scenes with shadows. In The Psychology of Computer Vision, Winston, P. H., ed. New York: McGraw-Hill.Google Scholar
Ward, A. C. 1988. A Theory of Quantitative Inference for Artifact Sets, Applied to a Mechanical Design Compiler. Department of Mechanical Engineering, MIT, Doctor of Science dissertation.Google Scholar