Cost Function

In classical planning, a cost function assigns a numerical cost to each primitive action. The planner's objective is to find a sequence of actions—a plan—whose summed action costs is minimized. This is the foundation for optimal pathfinding in deterministic environments.

• Example: In a logistics domain, moving a robot from point A to B might have a cost proportional to distance or energy consumed.
• Algorithmic Role: Heuristic search algorithms like A* use this cost (g(n)) combined with a heuristic (h(n)) to guide the search for the optimal plan.

Here, the cost function is typically framed as a negative reward function. The agent learns a policy that maximizes cumulative reward (or minimizes cumulative cost) over time. Costs are often delayed and probabilistic, defined by the Markov Decision Process (MDP) framework.

• Key Mechanism: The Bellman equation recursively defines the value of a state based on immediate cost/reward and the expected future cost of successor states.
• Objective: Find a policy π(s) that minimizes the expected discounted sum of future costs, where a discount factor (γ) weights immediate costs more heavily than distant ones.

In supervised learning, a cost function is called a loss function. It measures the discrepancy between the model's predictions and the true target values for a given training dataset. The learning process involves adjusting model parameters to minimize this loss.

• Common Examples: Mean Squared Error (MSE) for regression, Cross-Entropy Loss for classification.
• Optimization: Minimization is performed via iterative algorithms like gradient descent, which computes the gradient of the loss with respect to model parameters.

Cost functions define the objective in constrained optimization problems. The goal is to find variable assignments that minimize total cost (e.g., monetary expense, time) while satisfying a set of hard constraints.

• Applications: Supply chain logistics, scheduling, resource allocation.
• Formulation: Often expressed as a linear or integer programming problem: Minimize cᵀx subject to Ax ≤ b, where c is the cost vector.

The cost function is central to informed search algorithms. For a node n, the total estimated cost is f(n) = g(n) + h(n).

• g(n): The exact cost-to-come from the start node to n. This is the sum of action costs along the path.
• h(n): The heuristic estimate of the cost-to-go from n to the goal.
• Optimality Guarantee: If h(n) is an admissible heuristic (never overestimates), A* guarantees an optimal solution.

Real-world planning often involves balancing competing goals. A multi-objective cost function returns a vector of costs, one for each objective (e.g., [monetary_cost, time, risk]). There is rarely a single "best" plan, but a set of Pareto-optimal solutions.

• Pareto Frontier: The set of plans where improving one objective necessarily worsens another.
• Solution Methods: Include scalarization (weighting objectives) or algorithms like NSGA-II for finding the frontier.

A heuristic function estimates the remaining cost to reach a goal from a given state. Unlike a cost function, which measures the incurred cost of a path, a heuristic estimates the future cost. It is used to guide search algorithms like A* by prioritizing states that appear closer to the goal. An admissible heuristic never overestimates the true cost, guaranteeing that A* will find an optimal solution.

A Markov Decision Process is a mathematical framework for modeling sequential decision-making under uncertainty. It formalizes the planning problem with:

• A set of states and actions.
• Transition probabilities defining the likelihood of moving to a new state.
• A reward function (the inverse of a cost function) that provides immediate feedback for each state-action pair.
• The objective is to find a policy that maximizes the expected cumulative reward (or minimizes cumulative cost).

A* is a best-first graph search algorithm that finds a least-cost path by combining two functions:

• g(n): The exact, known cost from the start node to the current node n. This is the output of the cost function for the path taken.
• h(n): A heuristic function estimating the cost from n to the goal.
• The algorithm expands nodes with the lowest f(n) = g(n) + h(n) first. The cost function g(n) is critical for ensuring path optimality.

In complex planning, an agent often balances competing goals. Multi-objective optimization involves finding solutions that optimally trade off between multiple, often conflicting, cost functions. Instead of a single scalar cost, a plan is evaluated against a vector of objectives (e.g., [time_cost, monetary_cost, risk]). Solutions form a Pareto front, where no objective can be improved without worsening another. This is key for enterprise agents making business decisions.

A Constraint Satisfaction Problem involves finding an assignment of values to variables that satisfies a set of constraints. While not focused on minimizing a numeric cost, CSPs are a foundational planning paradigm. The concept of cost appears in Constraint Optimization Problems (COPs), where each solution has an associated cost, and the goal is to find a valid solution with minimal cost. This bridges logical feasibility with cost-based optimization.

A policy is a strategy that maps states (or belief states) to actions. In cost-minimization frameworks like MDPs, an optimal policy is one that minimizes the expected long-term cumulative cost. The policy is the output of the planning or learning process, while the cost function (or its inverse, the reward function) defines the criteria for optimality. In hierarchical planning, a policy may dictate which high-level task to decompose next based on estimated cost.