summaryrefslogtreecommitdiff
path: root/src/Agent.Planner
diff options
context:
space:
mode:
Diffstat (limited to 'src/Agent.Planner')
-rw-r--r--src/Agent.Planner/Agent.Planner.csproj1
-rw-r--r--src/Agent.Planner/AssemblyMarker.cs3
-rw-r--r--src/Agent.Planner/PlannerTask.cs18
-rw-r--r--src/Agent.Planner/PlannerTaskState.cs11
-rw-r--r--src/Agent.Planner/PlannerValidationException.cs3
-rw-r--r--src/Agent.Planner/TaskGraph.cs179
-rw-r--r--src/Agent.Planner/TokenBudgetClass.cs31
-rw-r--r--src/Agent.Planner/TokenEstimate.cs15
8 files changed, 261 insertions, 0 deletions
diff --git a/src/Agent.Planner/Agent.Planner.csproj b/src/Agent.Planner/Agent.Planner.csproj
new file mode 100644
index 0000000..6b512ec
--- /dev/null
+++ b/src/Agent.Planner/Agent.Planner.csproj
@@ -0,0 +1 @@
+<Project Sdk="Microsoft.NET.Sdk" />
diff --git a/src/Agent.Planner/AssemblyMarker.cs b/src/Agent.Planner/AssemblyMarker.cs
new file mode 100644
index 0000000..e90784d
--- /dev/null
+++ b/src/Agent.Planner/AssemblyMarker.cs
@@ -0,0 +1,3 @@
+namespace Agent.Planner;
+
+public static class AssemblyMarker;
diff --git a/src/Agent.Planner/PlannerTask.cs b/src/Agent.Planner/PlannerTask.cs
new file mode 100644
index 0000000..edc85c2
--- /dev/null
+++ b/src/Agent.Planner/PlannerTask.cs
@@ -0,0 +1,18 @@
+namespace Agent.Planner;
+
+public sealed record PlannerTask(
+ Guid Id,
+ string Description,
+ IReadOnlySet<Guid> Dependencies,
+ PlannerTaskState State,
+ TokenBudgetClass BudgetClass,
+ TokenEstimate Estimate,
+ long ActualInputTokens,
+ long ActualOutputTokens,
+ bool RequiresExternalEffect)
+{
+ public double ExpectedTokens => Estimate.ExpectedTokens;
+ public long ActualTotalTokens => checked(ActualInputTokens + ActualOutputTokens);
+}
+
+public sealed record CriticalPathResult(IReadOnlyList<Guid> TaskIds, double CumulativeTokenCost);
diff --git a/src/Agent.Planner/PlannerTaskState.cs b/src/Agent.Planner/PlannerTaskState.cs
new file mode 100644
index 0000000..d0b79bf
--- /dev/null
+++ b/src/Agent.Planner/PlannerTaskState.cs
@@ -0,0 +1,11 @@
+namespace Agent.Planner;
+
+public enum PlannerTaskState
+{
+ Queued,
+ Planning,
+ Running,
+ Completed,
+ Failed,
+ Cancelled
+}
diff --git a/src/Agent.Planner/PlannerValidationException.cs b/src/Agent.Planner/PlannerValidationException.cs
new file mode 100644
index 0000000..934d549
--- /dev/null
+++ b/src/Agent.Planner/PlannerValidationException.cs
@@ -0,0 +1,3 @@
+namespace Agent.Planner;
+
+public sealed class PlannerValidationException(string message) : InvalidOperationException(message);
diff --git a/src/Agent.Planner/TaskGraph.cs b/src/Agent.Planner/TaskGraph.cs
new file mode 100644
index 0000000..7a4d45b
--- /dev/null
+++ b/src/Agent.Planner/TaskGraph.cs
@@ -0,0 +1,179 @@
+namespace Agent.Planner;
+
+public sealed class TaskGraph(int maxTasks = 32)
+{
+ private readonly Dictionary<Guid, MutableTask> _tasks = [];
+ private readonly List<Guid> _insertionOrder = [];
+ private CriticalPathResult _criticalPath = new([], 0);
+
+ public int MaxTasks { get; } = maxTasks > 0 ? maxTasks : throw new ArgumentOutOfRangeException(nameof(maxTasks));
+ public int Count => _tasks.Count;
+ public CriticalPathResult CriticalPath => _criticalPath;
+ public long TotalTokenBudget => _tasks.Values.Aggregate(0L, static (total, task) => checked(total + task.BudgetClass.MaxTokens()));
+ public IReadOnlyList<PlannerTask> Tasks => _insertionOrder.Select(id => _tasks[id].Snapshot()).ToArray();
+
+ public PlannerTask AddTask(
+ string description,
+ TokenBudgetClass budgetClass,
+ TokenEstimate estimate,
+ IEnumerable<Guid>? dependencies = null,
+ bool requiresExternalEffect = false,
+ Guid? id = null)
+ {
+ if (string.IsNullOrWhiteSpace(description)) throw new PlannerValidationException("Task description is required.");
+ if (_tasks.Count >= MaxTasks) throw new PlannerValidationException($"Task limit of {MaxTasks} exceeded.");
+ estimate.Validate(budgetClass);
+ Guid taskId = id ?? Guid.NewGuid();
+ if (_tasks.ContainsKey(taskId)) throw new PlannerValidationException($"Task '{taskId}' already exists.");
+ HashSet<Guid> dependencySet = dependencies?.ToHashSet() ?? [];
+ EnsureDependenciesExist(dependencySet);
+ if (dependencySet.Contains(taskId)) throw new PlannerValidationException("A task cannot depend on itself.");
+
+ _tasks.Add(taskId, new MutableTask(taskId, description, dependencySet, budgetClass, estimate, requiresExternalEffect));
+ _insertionOrder.Add(taskId);
+ try
+ {
+ Recalculate();
+ }
+ catch
+ {
+ _tasks.Remove(taskId);
+ _insertionOrder.Remove(taskId);
+ throw;
+ }
+ return _tasks[taskId].Snapshot();
+ }
+
+ public void AddDependency(Guid taskId, Guid dependencyId)
+ {
+ MutableTask task = GetMutable(taskId);
+ EnsureMutable(task);
+ _ = GetMutable(dependencyId);
+ if (!task.Dependencies.Add(dependencyId)) return;
+ try
+ {
+ Recalculate();
+ }
+ catch
+ {
+ task.Dependencies.Remove(dependencyId);
+ throw;
+ }
+ }
+
+ public void SetEstimate(Guid taskId, TokenBudgetClass budgetClass, TokenEstimate estimate)
+ {
+ MutableTask task = GetMutable(taskId);
+ EnsureMutable(task);
+ estimate.Validate(budgetClass);
+ (TokenBudgetClass previousBudget, TokenEstimate previousEstimate) = (task.BudgetClass, task.Estimate);
+ task.BudgetClass = budgetClass;
+ task.Estimate = estimate;
+ try { Recalculate(); }
+ catch
+ {
+ task.BudgetClass = previousBudget;
+ task.Estimate = previousEstimate;
+ throw;
+ }
+ }
+
+ public void SetState(Guid taskId, PlannerTaskState state)
+ {
+ MutableTask task = GetMutable(taskId);
+ EnsureMutable(task);
+ task.State = state;
+ }
+
+ public void AddUsage(Guid taskId, long inputTokens, long outputTokens)
+ {
+ if (inputTokens < 0 || outputTokens < 0) throw new ArgumentOutOfRangeException(nameof(inputTokens), "Token usage cannot be negative.");
+ MutableTask task = GetMutable(taskId);
+ EnsureMutable(task);
+ task.ActualInputTokens = checked(task.ActualInputTokens + inputTokens);
+ task.ActualOutputTokens = checked(task.ActualOutputTokens + outputTokens);
+ }
+
+ public PlannerTask Get(Guid taskId) => GetMutable(taskId).Snapshot();
+
+ private void Recalculate()
+ {
+ IReadOnlyList<Guid> order = TopologicalOrder();
+ var costs = new Dictionary<Guid, double>();
+ var predecessors = new Dictionary<Guid, Guid?>();
+ foreach (Guid id in order)
+ {
+ MutableTask task = _tasks[id];
+ Guid? best = null;
+ double bestCost = 0;
+ foreach (Guid dependency in task.Dependencies.OrderBy(InsertionIndex))
+ {
+ double candidate = costs[dependency];
+ if (best is null || candidate > bestCost)
+ {
+ best = dependency;
+ bestCost = candidate;
+ }
+ }
+ costs[id] = bestCost + task.Estimate.ExpectedTokens;
+ predecessors[id] = best;
+ }
+ if (order.Count == 0)
+ {
+ _criticalPath = new([], 0);
+ return;
+ }
+ Guid end = order[0];
+ foreach (Guid id in order.Skip(1)) if (costs[id] > costs[end]) end = id;
+ var path = new List<Guid>();
+ for (Guid? current = end; current is not null; current = predecessors[current.Value]) path.Add(current.Value);
+ path.Reverse();
+ _criticalPath = new(path, costs[end]);
+ }
+
+ private IReadOnlyList<Guid> TopologicalOrder()
+ {
+ var indegree = _tasks.ToDictionary(static pair => pair.Key, static pair => pair.Value.Dependencies.Count);
+ var ready = new SortedSet<int>(_insertionOrder.Select((id, index) => (id, index)).Where(item => indegree[item.id] == 0).Select(static item => item.index));
+ var result = new List<Guid>(_tasks.Count);
+ while (ready.Count > 0)
+ {
+ int index = ready.Min;
+ ready.Remove(index);
+ Guid id = _insertionOrder[index];
+ result.Add(id);
+ foreach (Guid dependent in _insertionOrder.Where(candidate => _tasks[candidate].Dependencies.Contains(id)))
+ {
+ indegree[dependent]--;
+ if (indegree[dependent] == 0) ready.Add(InsertionIndex(dependent));
+ }
+ }
+ if (result.Count != _tasks.Count) throw new PlannerValidationException("TaskGraph must be a DAG; the update creates a cycle.");
+ return result;
+ }
+
+ private int InsertionIndex(Guid id) => _insertionOrder.IndexOf(id);
+ private MutableTask GetMutable(Guid id) => _tasks.TryGetValue(id, out MutableTask? task) ? task : throw new KeyNotFoundException($"Task '{id}' was not found.");
+ private void EnsureDependenciesExist(IEnumerable<Guid> dependencies)
+ {
+ foreach (Guid dependency in dependencies) _ = GetMutable(dependency);
+ }
+ private static void EnsureMutable(MutableTask task)
+ {
+ if (task.State == PlannerTaskState.Completed) throw new PlannerValidationException("Completed tasks are immutable.");
+ }
+
+ private sealed class MutableTask(Guid id, string description, HashSet<Guid> dependencies, TokenBudgetClass budgetClass, TokenEstimate estimate, bool requiresExternalEffect)
+ {
+ public Guid Id { get; } = id;
+ public string Description { get; } = description;
+ public HashSet<Guid> Dependencies { get; } = dependencies;
+ public PlannerTaskState State { get; set; } = PlannerTaskState.Queued;
+ public TokenBudgetClass BudgetClass { get; set; } = budgetClass;
+ public TokenEstimate Estimate { get; set; } = estimate;
+ public long ActualInputTokens { get; set; }
+ public long ActualOutputTokens { get; set; }
+ public bool RequiresExternalEffect { get; } = requiresExternalEffect;
+ public PlannerTask Snapshot() => new(Id, Description, Dependencies.ToHashSet(), State, BudgetClass, Estimate, ActualInputTokens, ActualOutputTokens, RequiresExternalEffect);
+ }
+}
diff --git a/src/Agent.Planner/TokenBudgetClass.cs b/src/Agent.Planner/TokenBudgetClass.cs
new file mode 100644
index 0000000..35894c7
--- /dev/null
+++ b/src/Agent.Planner/TokenBudgetClass.cs
@@ -0,0 +1,31 @@
+namespace Agent.Planner;
+
+public enum TokenBudgetClass
+{
+ K1 = 1_024,
+ K2 = 2_048,
+ K4 = 4_096,
+ K8 = 8_192,
+ K16 = 16_384,
+ K32 = 32_768,
+ K64 = 65_536,
+ K128 = 131_072
+}
+
+public static class TokenBudgetClassExtensions
+{
+ public static long MaxTokens(this TokenBudgetClass value) => (long)value;
+
+ public static TokenBudgetClass Parse(string value) => value switch
+ {
+ "1K" => TokenBudgetClass.K1,
+ "2K" => TokenBudgetClass.K2,
+ "4K" => TokenBudgetClass.K4,
+ "8K" => TokenBudgetClass.K8,
+ "16K" => TokenBudgetClass.K16,
+ "32K" => TokenBudgetClass.K32,
+ "64K" => TokenBudgetClass.K64,
+ "128K" => TokenBudgetClass.K128,
+ _ => throw new ArgumentOutOfRangeException(nameof(value), value, "Unknown token budget class.")
+ };
+}
diff --git a/src/Agent.Planner/TokenEstimate.cs b/src/Agent.Planner/TokenEstimate.cs
new file mode 100644
index 0000000..4b8920a
--- /dev/null
+++ b/src/Agent.Planner/TokenEstimate.cs
@@ -0,0 +1,15 @@
+namespace Agent.Planner;
+
+public readonly record struct TokenEstimate(long Optimistic, long MostLikely, long Pessimistic)
+{
+ public double ExpectedTokens => (Optimistic + (4d * MostLikely) + Pessimistic) / 6d;
+ public double VarianceTokens => Math.Pow((Pessimistic - Optimistic) / 6d, 2);
+
+ public void Validate(TokenBudgetClass budgetClass)
+ {
+ if (Optimistic <= 0 || Optimistic > MostLikely || MostLikely > Pessimistic || Pessimistic > budgetClass.MaxTokens())
+ {
+ throw new PlannerValidationException("Estimate must satisfy 0 < O <= M <= P <= token budget.");
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2026-10-19 18:07:57 +0000