Cloud Balancing — the Classic Bin-Packing Problem in LangGOAP

A Tier 2 tutorial that translates the classic cloud-balancing bin-packing problem into a LangGOAP A* + CSP pipeline.

The problem

Given a pool of computers and a set of processes, assign every process to exactly one computer such that:

• No computer exceeds its CPU, memory, or network capacity — hard per-resource constraints enforced by the CSP phase.

• The total USD cost is tracked as a soft objective that guides alternative-plan selection when the primary plan is infeasible.

The dataset below is a 4-process subset of a standard 2computers-6processes.json fixture, with per-process cost_usd values derived by dividing the original server costs by 10 (see the data module’s docstring for full provenance).

LangGOAP modelling

GOAP concept	Cloud balancing interpretation
ActionSpec	assign_<process>_to_<computer>
precondition	assigned_<process>=False
effect	assigned_<process>=True
resources	per-server cpu/mem/net + cost_usd
goal conditions	every process assigned
goal constraints (hard)	per-server capacity caps
goal objectives	minimize cost_usd

Pipeline behaviour

A* searches the plan space quickly — any assignment that flips every assigned_* flag to True is a valid A* solution. The CSP phase then:

1. Validates capacity. Resource totals are computed per server and checked against the hard constraints. If the primary plan fits, it is returned as-is (no alternative search).

2. Enumerates alternatives on infeasibility. When a constraint is violated, the CSP pipeline blacklists each action in the winning plan, re-runs A*, and asks CP-SAT to pick the cheapest feasible alternative — aligned with the cost_usd objective.

3. Surfaces status, never blocks. CSP is advisory: infeasible plans still execute, but the status and resource breakdown are attached to plan.metadata.csp for the caller to inspect.

import logging

# Suppress the advisory warning the CSP pipeline emits when primary and
# alternative plans are all infeasible — we demonstrate that case
# deliberately later in this notebook.
logging.getLogger("langgoap").setLevel(logging.ERROR)

from tutorial_examples.cloud_balancing import (
    cloud_balancing_actions,
    cloud_balancing_goal,
    cloud_balancing_start,
)
from tutorial_examples.data.cloud_balancing_instance import PROCESSES, SERVERS

from langgoap import CSPStatus, GoapGraph
from langgoap.planner.pipeline import plan as pipeline_plan

print("Servers:")
for s in SERVERS:
    print(f"  {s.name:14s} cpu={s.cpu:2d} mem={s.memory:2d} net={s.network:2d} cost/proc=${s.cost_usd_per_proc:6.0f}")
print("\nProcesses:")
for p in PROCESSES:
    print(f"  {p.name:4s} cpu={p.cpu} mem={p.memory} net={p.network}")

1. Action catalog

Every (process, computer) pair becomes a distinct ActionSpec. With 4 processes and 2 servers, the planner sees 8 actions — each consuming resources on its target server.

actions = cloud_balancing_actions()
print(f"Total actions: {len(actions)}")
for a in actions[:4]:
    print(f"  {a.name:34s} resources={dict(a.resources)}")

Total actions: 8
  assign_p0_to_server_big            resources={'cpu_server_big': 1.0, 'mem_server_big': 1.0, 'net_server_big': 1.0, 'cost_usd': 480.0}
  assign_p0_to_server_small          resources={'cpu_server_small': 1.0, 'mem_server_small': 1.0, 'net_server_small': 1.0, 'cost_usd': 66.0}
  assign_p1_to_server_big            resources={'cpu_server_big': 3.0, 'mem_server_big': 6.0, 'net_server_big': 1.0, 'cost_usd': 480.0}
  assign_p1_to_server_small          resources={'cpu_server_small': 3.0, 'mem_server_small': 6.0, 'net_server_small': 1.0, 'cost_usd': 66.0}

GOAP Execution Graph

The planner discovers a plan, the executor runs each action, and the observer checks progress — replanning automatically if something fails.

from IPython.display import Image, display

graph = GoapGraph(actions=actions)
display(Image(graph.compile().get_graph().draw_mermaid_png()))

2. Run the A* → CSP pipeline

langgoap.planner.pipeline.plan() runs A* first, then routes the result through the CSP validator. The returned Plan carries metadata.csp with status, resource usage breakdown, and constraint evaluations.

plan_obj = pipeline_plan(
    cloud_balancing_start(),
    cloud_balancing_goal(),
    actions,
)

print(f"CSP status: {plan_obj.metadata.csp.status.value}")
print(f"Plan:")
for step in plan_obj.actions:
    print(f"  {step.name}")

display(Image(plan_obj.draw_mermaid_png()))

3. Resource usage breakdown

CSPMetadata.resource_usage reports the aggregate total for every resource key touched by the plan. Because the A* search landed on a server_big-heavy assignment and server_big has abundant capacity, every hard constraint is satisfied and the primary plan is returned as-is. No alternative enumeration runs.

usage = {u.key: u.total for u in plan_obj.metadata.csp.resource_usage}

print("Per-server utilization (usage / capacity):")
for s in SERVERS:
    cpu = usage.get(f'cpu_{s.name}', 0)
    mem = usage.get(f'mem_{s.name}', 0)
    net = usage.get(f'net_{s.name}', 0)
    print(f"  {s.name:14s} cpu={cpu:3.0f}/{s.cpu:<3d} mem={mem:3.0f}/{s.memory:<3d} net={net:3.0f}/{s.network:<3d}")

print(f"\nTotal cost: ${usage.get('cost_usd', 0):.2f}")

Per-server utilization (usage / capacity):
  server_big     cpu=  6/24  mem=  9/96  net= 10/16 
  server_small   cpu=  0/6   mem=  0/4   net=  0/6  

Total cost: $1920.00

4. Forced placement via hard constraints

Process p1 requires 6 memory units — more than server_small provides (4). Any plan that places p1 on server_small would violate the mem_server_small ≤ 4 constraint. The CSP validator will reject such a plan, and the pipeline will enumerate alternatives to find a legal assignment for p1.

Let’s force the issue: start with every process except p1 pre-assigned to server_small so A* only has to place p1.

start = cloud_balancing_start()
# Pretend p0, p2, p5 are already running on server_small — valid because
# their combined cpu=3, mem=3, net=9 (note: net=9 would overflow server_small's
# net=6, but we won't re-validate the starting state here — we're only
# demonstrating that the planner picks server_big for p1 in isolation).
start_p1_only = dict(start)
start_p1_only["assigned_p0"] = True
start_p1_only["assigned_p2"] = True
start_p1_only["assigned_p5"] = True

plan_p1 = pipeline_plan(
    start_p1_only,
    cloud_balancing_goal(),
    actions,
)

assert plan_p1 is not None
p1_step = next(a for a in plan_p1.actions if "_p1_" in a.name)
print(f"p1 was placed on: {p1_step.name.rsplit('_to_', 1)[1]}")
print(f"(server_small mem=4 < p1.mem=6 → the only feasible computer is server_big)")

5. Infeasibility: a cost budget that can’t be met

The cheapest possible assignment (p1 on server_big, rest on server_small) still costs 480 + 66 * 3 = 678. Adding a hard cost_usd ≤ 100 constraint makes every candidate plan infeasible.

The CSP is advisory — the plan still executes, but the status is clearly recorded on plan.metadata.csp.

from langgoap import ConstraintSpec, GoalSpec
from langgoap.goals import ObjectiveDirection

tight_goal = GoalSpec(
    conditions={f"assigned_{p.name}": True for p in PROCESSES},
    constraints=(
        ConstraintSpec(key="cost_usd", max=100.0, level="hard"),
    ),
    objectives={"cost_usd": ObjectiveDirection.MINIMIZE},
)

tight_plan = pipeline_plan(
    cloud_balancing_start(),
    tight_goal,
    actions,
)

cost_usd = next(u.total for u in tight_plan.metadata.csp.resource_usage if u.key == 'cost_usd')
print(f"Budget:       $100.00")
print(f"Plan cost:    ${cost_usd:.2f}")
print(f"CSP status:   {tight_plan.metadata.csp.status.value}")

6. End-to-end via GoapGraph

For production deployments, you’d wire this up via GoapGraph and let LangGraph run the full plan → execute → observe loop. The executor applies the effects of each assignment in order, and the observer checks the goal conditions after every step.

result = GoapGraph(actions=actions).invoke(
    goal=cloud_balancing_goal(),
    world_state=cloud_balancing_start(),
)

print(f"Status:   {result['status']}")
assigned = sorted(k for k, v in result['world_state'].items() if v is True)
print(f"Assigned: {assigned}")

Status:   goal_achieved
Assigned: ['assigned_p0', 'assigned_p1', 'assigned_p2', 'assigned_p5']

Summary

• One problem instance, one LangGOAP action catalog. Each (process, computer) pair is a distinct ActionSpec; resources and constraints handle the bin-packing rules.

• A proposes, CSP disposes.* A* finds a plan fast; CSP validates capacity, enumerates alternatives on infeasibility, and picks the cheapest feasible option via CP-SAT.

• Forced placements come for free. Hard constraints catch illegal assignments (like p1 on server_small) without custom logic.

• CSP is advisory, not blocking. Infeasible plans still execute; status and resource breakdown are reported via plan.metadata.csp for callers to inspect.

Every scenario here is verified by tests/integration/test_cloud_balancing.py.