Constraint Programming for Component-Level Robot Design

Effective design automation for building robots would make development faster and easier while also less prone to design errors. However, complex multi-domain constraints make creating such tools difficult. One persistent challenge in achieving this goal of design automation is the fundamental problem of component selection, an optimization problem where, given a general robot model, components must be selected from a possibly large set of catalogs to minimize design objectives while meeting target specifications. Different approaches to this problem have used Monotone Co-Design Problems (MCDPs) or linear and quadratic programming, but these require judicious system approximations that affect the accuracy of the solution. We take an alternative approach formulating the component selection problem as a combinatorial optimization problem, which does not require any system approximations, and using constraint programming (CP) to solve this problem with a depth-first branch-and-bound algorithm. As the efficacy of CP critically depends upon the orderings of variables and their domain values, we present two heuristics specific to the problem of component selection that significantly improve solve time compared to traditional constraint satisfaction programming heuristics. We also add redundant constraints to the optimization problem to further improve run time by evaluating certain global constraints before all relevant variables are assigned. We demonstrate that our CP approach can find optimal solutions from over 20 trillion candidate solutions in only seconds, up to 48 times faster than an MCDP approach solving the same problem. Finally, for three different robot designs we build the corresponding robots to physically validate that the selected components meet the target design specifications.

Authors

• Andrew Wilhelm
• Nils Napp

Keywords

• Constraint handling
• Design automation
• Computational modeling
• Morphology
• Programming
• Approximation algorithms
• Quadratic programming
• Robot Design
• Constraint Programming
• Heuristic
• Optimization Problem
• Running Time
• Selection Problem
• Candidate Solutions
• Combinatorial Optimization Problem
• Robot Model
• Constraint Satisfaction
• Global Constraints
• Branch-and-bound Algorithm
• Endurance
• Design Process
• Search Space
• Multi-objective Optimization
• Solution Space
• Design Problem
• National Science Foundation
• Pareto Front Solutions
• Binary Constraints
• Constraint Satisfaction Problem
• Minimal Solution
• Constrained Optimization Problem
• Steep Incline
• Subset Of Variables
• Angular Speed
• Modular Components
• Lexicographic