Dantzig and PGS LCP Solver Implementations in DART: When to Use Each

DART provides two primary LCP solver categories—Dantzig (exact pivoting) for small-to-medium constraint problems requiring friction index support, and PGS (iterative projection) for large-scale real-time simulations—both selectable via WorldConfig in dart/simulation/world.hpp.

The Dynamic Animation and Robotics Toolkit (dartsim/dart) resolves contact forces, joint limits, and other constraints using linear complementarity problem (LCP) solvers. The repository ships with multiple LCP solver implementations that share a common interface but differ fundamentally in algorithmic approach, performance characteristics, and suitability for real-time applications.

Dantzig vs PGS: Core Differences

DART organizes LCP solvers into categories via the LcpSolver::getCategory() method. The two primary implementations represent opposing strategies: exact pivoting versus iterative projection.

Dantzig: Exact Pivoting Solver

The Dantzig solver is implemented in dart/math/lcp/pivoting/dantzig_solver.hpp and falls under the Pivoting category. It wraps a legacy principal-pivoting algorithm for boxed linear complementarity problems (BLCP).

• Deterministic exactness: Provides mathematically exact solutions for constraint satisfaction
• Friction index support: Correctly handles boxed LCPs with lower and upper bounds, including friction indices essential for Coulomb contact models
• Computational cost: Higher algorithmic complexity makes it unsuitable for large contact sets
• Best for: Offline simulations, verification runs, or scenarios with fewer than approximately 100 contacts where correctness outweighs speed

PGS: Projected Gauss-Seidel Solver

The PGS (Projected Gauss-Seidel) solver lives in dart/math/lcp/projection/pgs_solver.hpp and belongs to the Projection category. It uses an iterative relaxation method to approximate constraint solutions.

• Speed and bounded runtime: Very fast iterations with predictable execution time, ideal for hard real-time constraints
• Approximate solutions: Converges to a solution within tolerance rather than computing exact LCP results
• Warm-starting: Efficiently reuses previous frame solutions to accelerate convergence in temporal coherence scenarios
• Scalability: Handles hundreds to thousands of contacts efficiently
• Limitations: May require many iterations for tight tolerances and can struggle with highly stiff systems

When to Use Each LCP Solver Implementation

Choose Dantzig When:

• You require exact constraint satisfaction for problems involving box constraints (joint limits, contact with friction bounds)
• The simulation involves friction indices that must be resolved precisely for physical correctness
• You are running offline simulations or verification benchmarks where accuracy is paramount
• The contact set is small-to-medium (typically under 100 constraints)

According to dart/simulation/world.hpp (lines 83-104), Dantzig is the default primary LCP solver (LcpSolverType::Dantzig) in WorldConfig.

Choose PGS When:

• You are building real-time applications such as robotics control loops or interactive games with strict frame time budgets
• The simulation generates large contact sets where an approximate solution is acceptable
• You need a fallback solver when the primary exact solver fails to converge

The source code in dart/constraint/constraint_solver.cpp constructs PGS as the default secondary solver (WorldConfig::secondaryLcpSolver = LcpSolverType::Pgs), which activates when the primary solver cannot resolve constraints.

Configuring LCP Solvers in DART

Both solvers inherit from dart::math::LcpSolver and can be swapped at runtime through the WorldConfig struct or directly on constraint solver instances.

Setting Primary and Secondary Solvers

Configure solver selection during world creation via the configuration struct:

#include <dart/simulation/World.hpp>

int main()
{
  // Configure Dantzig as primary (exact) and PGS as fallback (fast)
  dart::simulation::WorldConfig cfg;
  cfg.primaryLcpSolver   = dart::simulation::WorldConfig::LcpSolverType::Dantzig;
  cfg.secondaryLcpSolver = dart::simulation::WorldConfig::LcpSolverType::Pgs;

  auto world = dart::simulation::World::create(cfg);

  // Note: Changing solvers after construction requires rebuilding the 
  // constraint solver internally via setPrimaryLcpSolver()
}

Per-Constraint Solver Override

For granular control, override the solver on specific BoxedLcpConstraintSolver instances as shown in dart/constraint/boxed_lcp_constraint_solver.cpp:

#include <dart/constraint/BoxedLcpConstraintSolver.hpp>
#include <dart/math/lcp/projection/pgs_solver.hpp>

auto boxedSolver = std::make_shared<dart::constraint::BoxedLcpConstraintSolver>();
boxedSolver->setLcpSolver(std::make_shared<dart::math::PgsSolver>());

Key Source Files and Architecture

Understanding the implementation locations helps when debugging or extending solver behavior:

• dart/simulation/world.hpp (lines 83-104): Defines the LcpSolverType enum and default primary/secondary assignments
• dart/math/lcp/pivoting/dantzig_solver.hpp: Wrapper for the principal-pivoting Dantzig algorithm
• dart/math/lcp/projection/pgs_solver.hpp: Implementation of the iterative Projected Gauss-Seidel algorithm
• dart/constraint/constraint_solver.cpp: Constructs default primary (DantzigSolver) and secondary (PgsSolver) instances
• dart/constraint/boxed_lcp_constraint_solver.cpp: Demonstrates runtime solver swapping logic

The architectural split between pivoting (exact, box-aware) and projection (iterative, fast) implementations allows DART to serve both high-fidelity physics research and real-time robotics applications.

Summary

• Dantzig provides exact solutions for boxed LCPs with friction support via pivoting algorithms in dart/math/lcp/pivoting/dantzig_solver.hpp, serving as the default primary solver for accuracy-critical simulations.
• PGS offers fast approximate solutions using iterative projection in dart/math/lcp/projection/pgs_solver.hpp, acting as the default secondary solver for real-time performance.
• Select solvers via WorldConfig::primaryLcpSolver and secondaryLcpSolver before world creation, or use BoxedLcpConstraintSolver::setLcpSolver() for per-instance control.
• Use Dantzig for small contact sets requiring exact friction handling; use PGS for large-scale or real-time scenarios where approximate solutions suffice.

Frequently Asked Questions

What is the default LCP solver in DART?

Dantzig is the default primary LCP solver, as defined in dart/simulation/world.hpp where WorldConfig initializes primaryLcpSolver to LcpSolverType::Dantzig. PGS serves as the default secondary (fallback) solver when the primary method fails to converge.

Can I switch between Dantzig and PGS at runtime?

Yes, both solvers implement the abstract dart::math::LcpSolver interface and can be swapped at runtime. You can modify the solver on a BoxedLcpConstraintSolver instance using setLcpSolver(), though changing the world's primary solver after construction requires rebuilding the internal constraint solver state.

Why does PGS struggle with highly stiff systems?

PGS is an iterative projection method that relaxes constraints gradually. Highly stiff systems create ill-conditioned matrices where variables change drastically between iterations, causing the Gauss-Seidel relaxation to converge slowly or oscillate. In these cases, the exact pivoting approach of Dantzig provides more reliable convergence, albeit at higher computational cost.

Where are the LCP solver implementations located in the DART source?

The Dantzig solver resides in dart/math/lcp/pivoting/dantzig_solver.hpp under the pivoting category, while the PGS implementation is in dart/math/lcp/projection/pgs_solver.hpp under the projection category. The selection logic and LcpSolverType enum are defined in dart/simulation/world.hpp, with instantiation logic in dart/constraint/constraint_solver.cpp.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}