Declarative Differential Models (DDM) refer to a modeling approach where the entire system's behavior—states, transitions, constraints, and objectives—is described declaratively and encoded directly within a set of differential equations or differential-algebraic equations (DAEs).
Key Features of DDM:
Declarative Nature:
The system is described by its rules and relationships, not step-by-step instructions.
These rules are translated into continuous or discrete dynamics that govern the system's evolution.
Constraint Embedding:
Logical and physical constraints (e.g., conservation laws, capacity limits) are directly included in the model equations.
This ensures the system operates within valid bounds without requiring external enforcement.
Dynamic and Adaptive Behavior:
DDMs can handle both deterministic and probabilistic transitions, making them suitable for hybrid systems (e.g., mixing continuous flows and discrete events).
Optimization-Friendly:
DDMs naturally integrate with optimization techniques, allowing parameters (e.g., transition rates) to be learned or fine-tuned directly within the model.
Examples and Applications:
Petri Nets: Encoding resource flows, transitions, and state changes as ODEs.
Hybrid Systems: Combining discrete decision-making with continuous dynamics.
Physics-Inspired Machine Learning: Embedding physical constraints within Neural ODEs.
Optimal Control: Modeling decision problems directly in the dynamics for optimization.
Why Declarative?
The term “declarative” emphasizes that the model focuses on what the system does (rules and behaviors) rather than how it does it (procedural steps).
Use Case Example:
In a knapsack optimization problem:
States represent item availability, weight, and value.
Transitions represent decisions to include/exclude items.
Constraints (e.g., weight capacity) are encoded directly into the model dynamics, making the system solvable and interpretable.
Continuous relaxation is a bridge between discrete and continuous domains, offering a powerful way to analyze complex problems by leveraging continuous mathematics. It is widely used across fields like optimization, physics, and systems modeling.
Using Continuous Relaxation with Petri Nets
Petri nets provide a robust framework for modeling the dynamics of Tic-Tac-Toe, extending beyond traditional game-tree analysis. By incorporating continuous relaxation, this approach transforms discrete moves and outcomes into a probabilistic system, making it possible to analyze strategic nuances using differential equations.
Modeling Tic-Tac-Toe as a Petri Net
In this model:
Places represent the grid's state, such as unclaimed cells (P00) and markers for Players X and O (e.g., X00 for Player X's mark in the top-left cell).
Transitions represent possible moves (e.g., Player X marking X00) and win conditions (e.g., X00_X01_X02 for a row win).
Tokens track the system's state, where a token in P00 indicates the top-left cell is unclaimed, while a token in X00 or O00 indicates it is marked by X or O.
Relaxing the System
Discrete moves are relaxed into continuous transitions, allowing the use of ODE solvers. For example:
A transition's firing rate represents the probability of a specific move, creating a probabilistic view of gameplay.
The win states (win_x, win_o) are modeled as accumulative probabilities derived from successful transition sequences.
Analyzing Strategies
By solving the ODEs, we can:
Predict Win Probabilities: The probabilities of win_x and win_o over time show the likelihood of each player achieving victory.
Evaluate Moves: The model ranks potential moves by their impact on the win probabilities, guiding optimal strategies.
Visualize Dynamics: Plots of win probabilities provide insights into how the game evolves based on current states and potential player decisions.
Conclusion
This Petri-net-based continuous relaxation approach brings a novel lens to Tic-Tac-Toe analysis. By transitioning from discrete moves to probabilistic trajectories, we uncover richer strategic insights and establish a framework applicable to more complex games and systems.
Review the code from previous post where we apply this approach using Juila and Petri.jl
Optimization problems, like the knapsack problem, often invite varied approaches. At first glance, advanced methods might seem complex compared to classic algorithms. Surprisingly, this isn’t always true. In this post, we compare two methods:
A continuous-time Petri net model using Ordinary Differential Equations (ODEs).
A branch-and-bound algorithm, a traditional combinatorial optimization technique.
While the Petri net approach appears advanced, it’s often simpler to implement and interpret, especially for dynamic systems.
Approach 1: Petri Net with ODEs
The Petri net model uses Petri.jl to represent the knapsack problem as a dynamic system:
States (places): Represent the items, weight, value, and capacity.
Transitions: Define how items are added based on resource constraints.
ODEs: Govern the rate of change, allowing for continuous simulation of token flows.
Why It Works:
Simplicity in Design: Defining states and transitions requires fewer lines of code compared to implementing a full algorithm.
Ease of Visualization: ODE solvers and plotting libraries make it easy to track how the knapsack evolves over time.
Dynamic Exploration: Exclusions (removing certain items) can be simulated by setting specific transition rates to zero, requiring only minor code changes.
Branch-and-bound is a powerful yet more traditional approach that systematically explores all possible solutions:
Tree Structure: Each node represents a decision (to include or exclude an item).
Bounds: Calculates upper and lower bounds to prune branches.
Iterative Exploration: Examines feasible solutions to maximize the knapsack's value.
Why It Works:
Proven Optimization: Guarantees an optimal solution by exhaustively exploring all branches.
Deterministic Results: No approximations or reliance on differential solvers.
Output from the branch-and-bound algorithm:
Maximal Value = 38
Which one to use?
For dynamic and exploratory analysis: The Petri net with ODEs is ideal. It offers a clear and flexible way to visualize how systems behave under various constraints.
For exact and guaranteed solutions: Branch-and-bound ensures optimality but comes with a higher implementation cost and less adaptability to dynamic changes.
Conclusion
While branch-and-bound excels in classic optimization, the Petri net approach proves that even advanced methods can be simpler and more intuitive in certain contexts. By leveraging tools like Petri.jl, we can tackle dynamic problems with ease, gaining insights without the overhead of intricate algorithms.
If you're diving into optimization or exploring Petri nets, try both methods and see which suits your needs. Continuous modeling might just surprise you with its simplicity and power.
In our previous post, we demonstrated how Petri.jl can model Tic-Tac-Toe by translating its states and transitions into a dynamic Petri net framework. By embedding win conditions into Ordinary Differential Equations (ODEs), we quantified move heuristics to evaluate the value of each opening move.
Heuristics: Quantifying Strategy
We calculated heuristic scores for all possible opening moves by Player X. The results highlight the strategic significance of each position:
This analysis validates Petri.jl as a robust tool for quantifying decision-making processes. Beyond games, it can model and optimize strategies in diverse domains.
Next Steps: Exploring Gossip Protocols
Having shown this technique works, we will now apply it to broader problems. Our next focus is modeling a simple gossip protocol to understand message propagation and consensus dynamics.
Stay tuned as we extend Petri.jl's capabilities to new frontiers of computational modeling!
Some time ago, we explored modeling the classic game of Tic-Tac-Toe as a Petri net, demonstrating how this formalism could elegantly represent the interplay between game states and transitions. Today, we revisit this idea with fresh insights and a more advanced approach using Petri.jl, a Julia library that offers powerful tools for constructing and analyzing Petri nets.
From Concept to Visualization
Petri.jl allows us to model Tic-Tac-Toe in a way that's both expressive and computationally robust. Below is a visualization of the Petri net we constructed for Tic-Tac-Toe:
This graph showcases the game states as places and the player moves as transitions. Each directed arc represents the flow of tokens—analogous to moves advancing the game toward its conclusion.
Revisiting the Formalism
At its core, the Tic-Tac-Toe model encapsulates the following:
Places: Represent the current state of the game (e.g., empty squares, player moves).
Transitions: Represent the legal moves available to each player.
Tokens: Indicate the state of play (e.g., which squares are occupied by X or O).
This approach highlights the game's structure, showing how states evolve as moves are made.
Analyzing Dynamics with ODEs
One of the most exciting possibilities opened up by Petri.jl is the ability to translate our Petri net into a system of Ordinary Differential Equations (ODEs). This enables a quantitative analysis of the game dynamics.
For
Each place corresponds to a variable representing the state of the board.
Transitions influence these variables based on player actions.
Solving the ODE system reveals trajectories of game progression.
Ensuring the Plot Matches the Game with Internal Win Conditions
The plots above appear to converge quickly to stable values, aligning with the game rules: the Next turn transition activates at t=1, and all moves settle to 0 starting at t=2. However, to confirm that this behavior accurately represents the game, we extended the Petri net model to include win conditions directly within the ODE system.
By embedding these conditions, we create a new ODEProblem that integrates both state dynamics and game logic. This approach ensures that the model can verify win outcomes internally, providing a stronger connection between the ODE-generated results and the expected behavior of Tic-Tac-Toe.
Model Checking X/O Win ratio
The extended model the Petri net to include places representing win conditions for each player. Each time a win condition was met, a token was deposited in the corresponding winx_ or wino_ place. After we solved and plotted the result, we measured this ratio at t=9.
Remarkably, the results showed only a 0.85% error compared to the expected statistical win ratios for Tic-Tac-Toe. This seems to demonst the model's accuracy in reflecting real-game dynamics.
Why This Matters
Revisiting our Tic-Tac-Toe model with modern tools like Petri.jl underscores how mathematical frameworks evolve alongside computational advancements. It also highlights the versatility of Petri nets in capturing not just static systems but also dynamic, strategy-driven games like Tic-Tac-Toe.
Next Steps
This approach is just the beginning. Future explorations could include:
Extending the model to other games with more complex rules.
Investigate how adding other Petri-net structures affect the dynamics of the ODE plots.
Python notebook with source code used in this post is available here
Pflow’s workflow implementation simplifies and extends WF-net ideas for practical, real-world systems by:
Adding retry and reentry mechanisms (allow_reentry).
Restricting state behaviors to enforce runtime constraints.
Focusing on execution rather than pre-runtime verification.
WF-nets remain a formal and abstract framework for analyzing workflows, often requiring specialized tooling and theoretical grounding. Pflow’s workflow model aligns more with runtime task automation and system engineering.
I then provided it as user input, alongside a system prompt:
Output models:
Remarks
I’m pretty impressed with how well OpenAI 4o performed.
The LLM correctly intuited that we’d like to use the state and action names as labels.
It also seemed to do a good job laying out the objects, and using the playground feature, I was even able to prompt another time to ask it to “add more space between the elements” – with consistent results.
Most of the other submissions made use of natural language translation and auto-classification.
Upon reflection: I could have applied the RAG approach using tools provided by Datastax, or built a tool using lang-graph, or even tried model refinement to get the results I wanted from Llama.
In the end, because OpenAI 4o worked with a single prompt I didn’t see any benefit to try to use Llama.
For now, I’ll be using 4o as I add LLM support to pflow.xyz.
Going forward, my sense is that various refinement approaches will become less relevant as better LLMs are developed, and for now the cost seems to be right for this application.
In the realm of software design, visualizing complex systems is paramount. Drawing inspiration from isometric projection—a drafting technique that represents three-dimensional objects in two dimensions—we can adopt a similar approach using Petri nets. This method offers a comprehensive perspective on system workflows and resources.
Isometric Projection: A Brief Overview
Isometric projection allows for the depiction of 3D objects on a 2D plane without distortion, maintaining equal scale along three axes. This technique provides a clear and detailed view of intricate structures, facilitating better understanding and analysis.
Petri Nets: Modeling System Dynamics
Petri nets are mathematical representations used to model distributed systems. They consist of places (depicting states), transitions (representing events), and arcs (indicating the flow between places and transitions). This framework effectively captures the dynamic behavior of systems, including concurrency and resource sharing.
Integrating Isometric Principles with Petri Nets
By applying the concept of isometric projection to Petri nets, we can create layered models that offer multiple perspectives of a system:
Primary Net: Illustrating the Overall Workflow
The primary Petri net serves as a high-level map of the system's main processes. It outlines the general flow, highlighting key transitions and states. This top-level view provides a clear understanding of the system's core functionality.
Sub-Nets: Detailing Resources and Sub-Workflows
Sub-nets delve into specific components, such as resources or subsidiary workflows. Each sub-net focuses on a particular aspect, offering detailed insights into its operations and interactions. This modular approach simplifies complex systems by breaking them down into manageable sections.
Composite View: Achieving a Comprehensive Projection
Combining the primary net with its associated sub-nets results in a holistic representation of the system. This integrated model mirrors the clarity of an isometric projection, allowing for simultaneous examination of the system's overall structure and its detailed components.
Advantages of This Approach
Enhanced Clarity: Layered modeling clarifies complex systems, making them easier to understand and analyze.
Modularity: Sub-nets enable focused examination of individual components, facilitating targeted development and troubleshooting.
Scalability: This method accommodates system growth, allowing for the addition of new sub-nets as the system evolves.
Conclusion
Embracing the principles of isometric projection through the use of Petri nets offers a structured and comprehensive approach to software design. This technique not only enhances visualization but also improves the management and scalability of complex systems.
This blog post is NOT about LLMs!! The term Model is barely mentioned now-a-days without a prefix — as “Large Language Models” have reshaped the technical landscape.
A model is an abstract representation of a process that is composed of both behaviors (actions) and attributes (data). A good model allows for a system to be more predictable and easier to understand. A great model can also reduce the code complexity of a program.
Building Functional Models
Functional programming philosophy tells us that any problem can be solved via a reductionist approach: the developer decomposes a problem into functions, and then re-composes those functions into a solution.
This same paradigm is can be formally applied using petri-net models. First, we model the problem to be solved as a series of events. Then, by linking actions with input and output states, we compose these events into a full solution.
Net Analysis
Petri-nets are a formal analysis tool providing a formal foundation at design time, but we can also use them to make assertions about our program at runtime.
One useful attribute for analysis is reachability:
Given an input state, can the petri-net state machine be transformed into a target state?
Another testable property is boundedness:
Does this net model a closed system? Can a given place ever hold more than N tokens? Does the system ever create or destroy tokens?
The last property we hilight is liveness:
Can the network reach a state where no transformations are possible? under what conditions does the network reach this halting state?
Many of these properties can be analyzed through simulation. The petri-net itself is an executable schema. Pflow leverages this ability to interact with a model as a way to let users perform these checks simply by running model in a browser.
Conclusion
Building models into our code can improve design and the execution. Small models are comprehensible a user and developer alike. For a software developer, using a state machine for problem solving applies rigor at both design-time and program runtime. As a user, models can inform and educate about the state of a running process while interacting with a program. Check out the resources below how to use models in your code:
By solving the ODEs, we can:
For
