% Upper-case A B C D E F G H I J K L M N O P Q R S T U V W X Y Z % Lower-case a b c d e f g h i j k l m n o p q r s t u v w x y z % Digits 0 1 2 3 4 5 6 7 8 9 % Exclamation ! Double quote " Hash (number) # % Dollar $ Percent % Ampersand & % Acute accent ' Left paren ( Right paren ) % Asterisk * Plus + Comma , % Minus - Point . Solidus / % Colon : Semicolon ; Less than < % Equals = Greater than > Question mark ? % At @ Left bracket [ Backslash \ % Right bracket ] Circumflex ^ Underscore _ % Grave accent ` Left brace { Vertical bar | % Right brace } Tilde ~ % ---------------------------------------------------------------------| % --------------------------- 72 characters ---------------------------| % ---------------------------------------------------------------------| % % Optimal Foraging Theory Revisited: Chapter 1. Model of a Solitary % Agent % % (c) Copyright 2007 by Theodore P. Pavlic % \chapter{Model of a Solitary Agent} \label{ch:model}% \index{solitary agent model|(}% \index{agent model|see{solitary agent model}}% \index{stochastic model|see{solitary agent model}}% \index{foraging model|see{solitary agent model}}% \index{model|see{solitary agent model}}% \index{foraging|see{optimal foraging theory}}% \index{optimal foraging theory|(}In this chapter, we present a \index{stochasticity}stochastic model of a typical solitary agent (\ie, neither competition nor cooperation is modeled) as a generalization of the one described by \citet{Cha73}. This model is similar to numerous deterministic and stochastic foraging models in the ecology literature \citep[\eg,][]{Cha76, ChaMantid, Hughes79, Pulliam74, Pulliam75, Schoener71, WH74}; we focus on the model of \citeauthor{Cha73} because its high level of mathematical rigor lets it encompass many features of most other models in a theoretically convincing way. Introducing additional generality to this model allows it to be used in a wider range of applications that have different optimization criteria than classical \ac{OFT}. We also suggest a new way of deriving statistics for this model based on a fixed number of tasks \emph{processed}. This differs from the conventional statistical approach in \ac{OFT} which focusses on statistics based on a fixed number of tasks \emph{encountered} regardless of processing. Our approach has wider application to engineering and provides a new way of handling analysis of finite-lifetime behavior.\index{optimal foraging theory|)} Below, we introduce terminology that will be used throughout this document and give the motivations for our approach. The model is presented in \longref{sec:general_model}. In \longref{sec:classical_oft_model}, we describe the analytical approach used in classical \ac{OFT}. We present our approach as a modification to the classical \ac{OFT} method in \longref{sec:processing_only_model}. Interesting relationships between the two methods are given in \longref{sec:relationship_bw_approaches}. Finally, weaknesses of this model (and thus also of both approaches) are given in \longref{sec:model_weaknesses}. A list of some frequently used terms in this model and the two approaches is given \hyperref[ch:terms]{at the end of this document}. \subsubsection{Terminology: Agents, Tasks, and Currency} \index{agent|see{solitary agent model, agent}}\index{searching|see{solitary agent model, searching}}\index{tasks|see{solitary agent model, tasks}}\index{processing|see{solitary agent model, processing}}\index{point gain|see{solitary agent model, point gain}}\index{costs|see{solitary agent model, costs}}\index{currency|see{solitary agent model, currency}}\index{net point gain|see{solitary agent model, net point gain}}The model we use describes a generic \index{solitary agent model!agent|indexdef}\emph{agent} that \index{solitary agent model!searching|indexdef}\emph{searches} at some constant rate for \index{solitary agent model!tasks|indexdef}\emph{tasks} to \index{solitary agent model!processing|indexdef}\emph{process} in an effort to acquire \index{gain|see{solitary agent model, point gain}}\index{solitary agent model!point gain|indexdef}\emph{point gain}. The agent is assumed to be able to detect all potential tasks perfectly. During both searching and processing, the agent may have to pay \index{solitary agent model!costs|indexdef}\emph{costs}; however, the agent will pay no cost to detect the tasks. The point gain and costs will be given in the same \index{solitary agent model!currency|indexdef}\emph{currency}, and so \index{solitary agent model!net point gain|indexdef}\emph{net point gain} will be the difference between point gain and costs. For example, this model could describe an animal foraging for energetic gain at some energetic cost, or it could describe an \index{examples!applications!autonomous vehicle}autonomous military vehicle searching for targets at the expense of fuel. \subsubsection{Behavioral Optimization: Making the Best Choices} When an agent encounters a task, we refer to making a \index{choice|see{solitary agent model, choice}}\index{solitary agent model!choice|indexdef}\emph{choice} among different behavioral options within the model for processing that task. Despite this naming convention, we do not imply that the agent needs to have the cognitive ability to make choices; the agent only needs to behave in some consistent manner. We then can build performance measures over the space of these behaviors. In a biological context, these performance measures may model reproductive success. In an engineering context, these performance measures may, for example, measure the relative importance of various tasks with respect to the fuel cost required to complete them. Whether through natural selection or engineering design, behaviors that optimize these performance measures should be favored. \subsubsection{Approach Motivation: Finite Lifetime Analysis and Design} \index{optimal foraging theory|(}\index{solitary agent model!processing-only analysis|(}Our model is more than just semantically different than the classical \ac{OFT} model originally introduced by \citet{Cha73} and popularized by \citet{SK86}. For one, it takes parameters from a wider range of values and replaces deterministic aspects of the \ac{OFT} model with first-order statistics of random variables. More importantly, our new approach to analysis provides a convenient method for analyzing behavior over a \emph{finite} lifetime (or \emph{runtime} in an engineering context). Classical \ac{OFT} does not attempt to analyze finite lifetimes. Instead, limiting statistics on a space of never-ending behaviors are used. It is natural to define a finite lifetime as a finite number of tasks processed. However, classical \ac{OFT} focusses its analysis on cycles that start and end on task encounters regardless of whether those encounters lead to processing. In our approach, we recognize that because the agent does not pay a recognition cost on each encounter, all encounters that do not result in processing may be discarded. Because we consider only the encounters that result in processing, a finite lifetime can be defined as a finite number of these encounters. This can be useful, for example, if processing a task involves depositing one of a limited number of objects.\index{solitary agent model!processing-only analysis|)}\index{optimal foraging theory|)}\index{solitary agent model|)} \section{The Generalized Solitary Agent Model} \label{sec:general_model}% \index{randomness|see{stochasticity}}% \index{probability|see{stochasticity}}% \index{solitary agent model|(indexdef} An agent's lifetime is a random experiment modeled by the \index{probability space|see{stochasticity, probability space}}probability space\footnote{\index{stochasticity!probability space|(indexdef}A \emph{probability space} is a set of outcomes, a set of events that each are a set of outcomes, and a \index{probability measure|see{stochasticity, probability measure}}\index{stochasticity!probability measure|indexdef}measure mapping those events to their probability.\index{stochasticity!probability space|)indexdef}} $(\set{U}, \Pow(\set{U}), \Pr)$. That is, each outcome $\zeta \in \set{U}$ represents one possible lifetime for the agent, and so we will often substitute the term \emph{lifetime} for the term \emph{outcome}. Thus, statistics on \index{random variables|see{stochasticity, random variables}}random variables\footnote{\index{stochasticity!random variable|(indexdef}A \emph{random variable} $X$ is a measurable function mapping events into \index{Borel sets|see{mathematics, sets, Borel algebra}}\aimention{\'{E}mile Borel}Borel sets of \index{numbers|see{mathematics, numbers}}\index{real numbers|see{mathematics, numbers, real numbers}}real numbers.\index{stochasticity!random variable|)indexdef}} in this probability space will include parameters that fully specify the environment and the agent's behavior. For example, if the agent acquires gain over its lifetime, the \index{stochasticity!statistics!expected value|see{stochasticity, statistics, expectation}}\index{stochasticity!statistics!mean|see{stochasticity, statistics, expectation}}\index{expected value|see{stochasticity, statistics, expectation}}\index{expectation|see{stochasticity, statistics, expectation}}\index{mean|see{stochasticity, statistics, expectation}}\index{average|see{stochasticity, statistics, expectation}}expected% \footnote{\index{stochasticity!statistics!expectation ($\E$)|(indexdef}The \emph{expectation} $\E(X)$ is $\int_{-\infty}^\infty x f_X(x) \total x$ where $f_X$ is the (\aimention{Henri L. Lebesgue}Lebesgue) probability density of events under $X$. The expectation is often called the \emph{mean} or the \emph{(first) \index{moments|see{stochasticity, statistics, moments}}\index{stochasticity!statistics!moments|indexdef}moment (about the origin)}. It represents the \emph{center} of mass of the distribution.\index{stochasticity!statistics!expectation ($\E$)|)indexdef}} gain represents the probabilistic average of all possible gains given the agent's behavior and the randomness in the environment. The optimization goal will be to choose behavioral parameters that yield the optimum statistics in the given environment. \subsection{Model Assumptions} \label{sec:model_assumptions} \index{model assumptions|see{solitary agent model, assumptions}}\index{assumptions|see{solitary agent model, assumptions}}\index{solitary agent model!assumptions|(indexdef}An agent's lifetime (\ie, each random outcome in the model) consists of searching for tasks, choosing whether to process those tasks, processing those tasks, receiving gains for processing those tasks, and paying costs for searching and processing. The following are general assumptions about these aspects of the agent's interaction with its environment. % \index{uncorrelated random variables|see{stochasticity, random variable, uncorrelated}}% \index{independent random variables|see{stochasticity, random variable, independent}}% \begin{description} \item\emph{Independent Processing Cost Rates:} Processing costs are linear in processing time, and so they are completely specified by \emph{processing cost rates}. We assume these cost rates are uncorrelated\footnote{\index{stochasticity!random variable!uncorrelated|(indexdef}To say random variables $X$ and $Y$ are uncorrelated means $\E(XY)=\E(X)\E(Y)$.\index{stochasticity!random variable!uncorrelated|)indexdef}} with any length of (processing) time, and that the processing cost of any particular task is independent\footnote{\index{stochasticity!random variable!independence|(indexdef}To say random variables $X$, $Y$, and $Z$ are (mutually) independent means that $f_{XYZ}(x,y,z) = f_X(x) f_Y(y) f_Z(z)$. This implies that they are uncorrelated and that $\E(X|Y)=\E(X)$.\index{stochasticity!random variable!independence|)indexdef}} of the processing cost of any other task. \item\emph{Independent Processing Gains:} The processing gain for any particular task is independent of the processing gain of any other task. \item\emph{Independent Processing Decisions:} An agent's decision to process any particular task is independent of its decision to process any other task. \item\emph{Pseudo-Deterministic Search Cost Rate:} The search cost for finding any particular task is assumed to be independent of the type of that task and independent of the search cost of finding any other task. Additionally, search costs are assumed to be linear in search time, and so they are completely specified by \emph{search cost rates}. We make several assumptions about these rates. % \begin{itemize} \item Search cost rates are uncorrelated with any length of time. \item For any lifetime $\zeta \in \set{U}$, the search cost rate is a single random variable rather than some kind of random process. In other words, we assume the search cost rate is constant over the entire lifetime of an agent. Thus, we consider the search cost rate to be the random variable $C^s: \set{U} \mapsto \extR$. \item We define $c^s \in \R$ as the expectation of random variable $C^s$ (\ie, $c^s = \E(C^s)$), so $c^s$ is finite. \item \index{pseudo-deterministic|see{stochasticity, random variable, pseudo-deterministic}}% \index{stochasticity!random variable!pseudo-deterministic|(indexdef} We assume $\Pr( C^s = c^s ) = 1$. This is roughly equivalent to assuming that $C^s$ is deterministic. This assumption is critical for the analyses of variance and stochastic limits in the model; if neither of these is of interest, then this assumption can be relaxed entirely.\index{stochasticity!random variable!pseudo-deterministic|)indexdef} \end{itemize} % Thus, in many cases, the parameter \termdef{Aenv}{searchcost}{$c^s$}{Average cost rate for searching (points per second)} will be an acceptable surrogate for the phrase \emph{search cost rate} or even \emph{search cost} as long as it is understood to be a rate. \end{description} \index{solitary agent model!assumptions|)indexdef} \subsection{Task-Type Parameters} \label{sec:tt_params} Tasks encountered by an agent during its lifetime are grouped into types that share certain characteristics. In particular, there are \termdef[$n \in \N$]{Aenv}{numtypes}{$n$}{Number of task types} distinct task types. Take $i \in \{1,2,\dots,n\}$. % \begin{description} \item\emph{Task-Type Processes:} \index{solitary agent model!random processes|(indexdef}For task type $i$, encounters are driven by a \aimention{Sim\'{e}on-Denis Poisson}Poisson process $(M_i(t_s):t_s \in \R_{\geq0})$. That is, for each lifetime $\zeta \in \set{U}$, $M_i(t_s)$ is the number of encounters with tasks of type $i$ after $t_s \in \R_{\geq 0}$ units of \emph{search time}. We associate the following sequences of \index{mutually independent and identically distributed (\iid)|see{stochasticity, random variable, \iid}}\index{independent and identically distributed (\iid)|see{stochasticity, random variable, \iid}}\index{iid@\iid|see{stochasticity, random variable, \iid}}\acro[\index{stochasticity!random variable!iid@\iid|indexdef}(mutually) independent and identically distributed~(\iid)]% [IID]{\iid}{\index{stochasticity"!random variable"!iid"@\iid"|indexglo}(mutually) independent and identically distributed}\ random variables with \index{finite expectation|see{stochasticity, statistics, finite expectation}}\index{stochasticity!statistics!finite expectation}finite expectation% \footnote{\index{stochasticity!statistics!finite expectation|(indexdef}To say random variable $X$ has finite expectation means that $\E(|X|) < \infty$.\index{stochasticity!statistics!finite expectation|)indexdef}} with this \aimention{Sim\'{e}on-Denis Poisson}Poisson process. % \begin{itemize} \item $(I^i_M)$: Random process representing the type of the task. That is, $I^i_M = i$ for all $N \in \N$ and all $\zeta \in \set{U}$. \item $(g^i_M)$: Random process representing potential gross processing gains (\ie, the gross gain rewarded if the task is chosen for processing) for encounters with tasks of type $i$. \item $(\tau^i_M)$: Random process representing potential processing times (\ie, the processing time if the task is chosen for processing) for encounters with tasks of type $i$. \item $(c^i_M)$: Random process representing potential cost rates (\ie, the cost rate for processing time if the task is chosen for processing) for encounters with tasks of type $i$. Thus, $(c^i_M T^i_M)$ is a random process of potential costs (\ie, the processing cost if the task is chosen for processing) for encounters with tasks of type $i$. \item $(X^i_M)$: Random process representing the agent's choice to process a task of type $i$ immediately after encountering it. That is, for encounter $N \in \N$ of lifetime $\zeta \in \set{U}$, % \begin{equation*} X^i_M = \begin{cases} 0 &\text{if the agent chooses not to process the task}\\ 1 &\text{if the agent chooses to process the task} \end{cases} \end{equation*} % We make several assumptions about this process. % \begin{enumerate}[(i)] \item For all $N \in \N$, $\E(X^i_M)=1$ if and only if $X^i_M(\zeta)=1$ for all $\zeta \in \set{U}$. \item For all $N \in \N$, $\E(X^i_M)=0$ if and only if $X^i_M(\zeta)=0$ for all $\zeta \in \set{U}$. \item Each processing choice is independent of all other processing choices. \item For $M \in \N$, $X_M$ is uncorrelated with $(g^i_M - c^i_M \tau^i_M)$, $c^i_M \tau^i_M$, and $\tau^i_M$. \end{enumerate} % It is clear that $(X^i_M)$ is a sequence of \aimention{Jacob Bernoulli}Bernoulli trials. \end{itemize} % \index{solitary agent model!random processes|)indexdef} \item\emph{Parameters of Task Types:}\index{solitary agent model!parameters|(indexdef}The above random processes are characterized by the parameters below. Tasks within a particular type all share these parameters; that is, these parameters also characterize each task type. % \begin{itemize} \item \termdef[$\lambda_i \in \R_{>0}$]% {Atypes.0}{lambdai}{$\lambda_i$}{% \aimention{Sim\'{e}on-Denis Poisson}Poisson encounter rate for task type $i$ (tasks per second)}: The \aimention{Sim\'{e}on-Denis Poisson}Poisson rate for process $(M_i(t_s):t_s \in \R_{\geq0})$ (\ie, $\lambda_i = 1/\E(T^i_1)$). An expanded version of this model might introduce detection errors by modulating this parameter, which might also be made to depend on search speed. \Citet{PP06} incorporate both of these aspects with the analogous parameter of a similar agent model. \item \termdef[$\tau_i \in \R$]% {Atypes.1}{typeprtime}{$\tau_i$}{Average processing time for task type $i$ (seconds per task)}: The average processing time, given in seconds, for processing a task of type $i$ (\ie, $g_i = \E(\tau^i_1)$). \item \termdef[$c_i \in \R$]% {Atypes.01}{typecostrate}{$c_i$}{Average fuel cost rate for task type $i$ (points per second per task)}: The average fuel cost rate, given in points per second, for processing a task of type $i$ (\ie, $c_i = \E(c^i_1)$). \item \termdef[$g_i \in \R$]% {Atypes.01}{typegain}{$g_i$}{Average gross processing gain for task type $i$ (points per task)}: The average gross gain, given in points, for processing a task of type $i$ (\ie, $g_i = \E(g^i_1)$). \item \termdef[{$p_i \in [0,1]$}]% {Atypes.1}{typeprefprob}{$p_i$}{The agent's preference probability for task type $i$}: An agent's preference for processing a task of type $i$. % \begin{itemize} \item If $p_i = 0$, then no tasks of type $i$ are processed. \item If $p_i \in (0,1)$, then tasks of type $i$ are processed according to successes of a \aimention{Jacob Bernoulli}Bernoulli trial with parameter $p_i$. \item If $p_i = 1$, then all tasks of type $i$ are processed. \end{itemize} % That is, $p_i$ can be called the probability that the agent will process a task of type $i$ (\ie, $\E(X^i_1)=p_i$). Detection errors could be introduced via this parameter as well. \end{itemize} % Of course, it is trivial that $\E(I^i_1) = i$. \item\emph{Average Gain as Function of Average Time:} Unlike with processing costs, the relationship between processing time and processing gain has not been made explicit. In general, the model of the system will require $g_i$ to change whenever $\tau_i$ changes. That is, it makes sense that a longer average processing time would alter the average gain. Therefore, we introduce the function $g_i: \R_{\geq0} \mapsto \R$ so that \termdef{Atypes.111}{typegainfn}{$g_i(\tau_i)$}{Average processing gain for task type $i$ as function of average processing time} represents the average gain returned from tasks of type $i$ given an average processing length of $\tau_i \in \R_{\geq0}$. This function is used when predicting the optimal processing time in a given environment. We usually assume $g_i$ is continuously differentiable. \index{solitary agent model!parameters|)indexdef} \item\emph{Optimization Variables and Prey and Patch Models:} \index{solitary agent model!decision variables|(indexdef}The behavior of an agent is completely specified by the preference probabilities (\ie, $p_i$ for all $i \in \{1,2,\dots,n\}$) and the processing times (\ie, $\tau_i$ for all $i \in \{1,2,\dots,n\}$). All other parameters are fixed with the agent's environment. The \index{task processing-length choice problem}\emph{task processing-length choice problem} refers to the case when the preference probabilities are also fixed with the environment (\ie, absorbed into the task type encounter rates) so that the agent is free to choose processing times only; this is called a \index{patch model|see{task processing-length choice problem}}\emph{patch model} by biologists \citep{SK86}. The \index{task-type choice problem}\emph{task-type choice problem} refers to the case when the processing times are fixed with the environment so that the agent is free to choose preference probabilities only; this is called a \index{prey model|see{task-type choice problem}}\emph{prey model} by biologists \citep{SK86}. The most general case, when the agent is free to choose both, is called the \index{combined task-type and processing-length choice problem}\emph{combined task-type and processing-length choice problem}; biologists refer to this case as the \index{combined prey and patch model|see{combined task-type and processing-length choice problem}}\emph{combined prey and patch model} \citep{SK86}.\index{solitary agent model!decision variables|)indexdef} \end{description} % These processes and parameters will be used throughout this document. \subsection{Actual Processing Gains, Costs, and Times} \index{solitary agent model!random processes|(indexdef} Take $i \in \{1,2,\dots,n\}$. For the rest of this chapter, we will also use the processes $(G^i_M)$, $(C^i_M)$, and $(T^i_M)$, which are defined with $G^i_M \triangleq X^i_M g^i_M$ and $C^i_M \triangleq X^i_M c^i_M \tau^i_M$ and $T^i_M \triangleq X_i^n \tau^i_M$ for all $\zeta \in \set{U}$ and $N \in \N$. These represent the actual processing gain, processing cost, and processing time for each task encounter. Clearly, the gain (processing time) of any task is independent of the gain (processing time) of any other task; additionally, $(G^i_M)$, $(C^i_M)$, and $(T^i_M)$ are sequences of \iid{}\ random variables with \index{stochasticity!statistics!finite expectation}finite expectation. It is necessary for \index{stochasticity!random variable!pseudo-deterministic}$\Pr(C^s=c^s)=1$ for the random variables of $(G^i_M)$ and $(C^i_M)$ to be \iid{}. If this is not the case, then the random variables of $(G^i_M)$ and $(C^i_M)$ will be identically but \index{stochasticity!random variable!independence}not independently distributed.\index{solitary agent model!random processes|)indexdef}\index{solitary agent model|)indexdef} \subsection{Important Technical Notes} \index{solitary agent model|(} \index{optimal foraging theory|(}This model has more flexibility than the classical \ac{OFT} models described by \citet{SK86}. It also shares one aspect of classical \ac{OFT} foraging models that is often taken for granted. % \begin{description} \item\emph{Enhanced Gain and Cost Structure:} We augment the conventional classical \ac{OFT} foraging model with time-dependent costs, while not restricting the signs of our cost and gains. That is, we allow costs and gains to be positive, zero, or negative. In other words, negative costs may be viewed as time-dependent gains just as negative gains may be viewed as time-constant costs. For example, a negative search cost may be viewed as modeling the value of some other useful activity that can only be done during searching. Some impacts of this generalization of the gain and cost structure are discussed in \longref{ch:optimization_objectives}. \item\emph{\aimention{Sim\'{e}on-Denis Poisson}Poisson Processes and Simultaneous Encounters:} All of the assumptions listed in \longrefs{sec:model_assumptions} and \shortref{sec:tt_params} are important, but one particular assumption (that is also found in the classical solitary foraging model) deserves special attention, namely that model encounters occur according to a \aimention{Sim\'{e}on-Denis Poisson}Poisson process. A consequence of this assumption is that interarrival times have a particular continuous distribution. Additionally, this assumption implies that simultaneous encounters occur with probability zero; therefore, behavioral statistics are not affected by the choices made by the agent on a simultaneous encounter. \end{description} \index{optimal foraging theory|)} \section{Classical OFT Analysis: Encounter-Based Approach} \label{sec:classical_oft_model}\index{optimal foraging theory|(}% \index{solitary agent model!classical analysis|(indexdef} Here, we introduce an approach to analysis of agent behavior based on classical \ac{OFT} \citep[\eg{},][]{Cha73,SK86}. We call this a \index{merge before split approach}\emph{merge before split} approach. In this approach, the encounter rates of each type are independent of the preference probabilities. That is, the agent is considered to encounter each task and then choose whether to process the task. Because encounters are generated by \aimention{Sim\'{e}on-Denis Poisson}Poisson processes, an alternative approach would be to make the preference probabilities a modifier of the encounter rates rather than some aspect of the agent's choice; this alternative is described in \longref{sec:processing_only_model}. The merged processes generated by encounters with all tasks are described in \longref{sec:classical_oft_merge}. \longrefs{sec:oft_model_markov_renewal_process}, \shortref{sec:oft_markov_renewal_reward_processes}, and \shortref{sec:oft_reward_process_stats} use renewal theory based on these merged processes to develop statistics that can be used as optimization criteria for agent behavior. \subsection{Processes Generated from Merged Encounters}% \label{sec:classical_oft_merge}% \index{solitary agent model!classical analysis!Poisson encounters|(indexdef} Above, we defined $n$ \aimention{Sim\'{e}on-Denis Poisson}Poisson processes corresponding to the $n$ task types. However, as an agent searches, it encounters tasks from $n$ processes at once. That is, the agent faces the \index{merged Poisson process|see{stochasticity, Poisson process, merged}}\index{stochasticity!Poisson process!merged}merged \aimention{Sim\'{e}on-Denis Poisson}Poisson process $(M(t_s) : t_s \in \R_{\geq0})$ defined for all $\zeta \in \set{U}$ and all $t_s \in \R_{\geq0}$ by % \begin{equation*} M(t_s) \triangleq \sum\limits_{i=1}^n M_i(t_s) \end{equation*} % which carries with it the interevent time process $(\Upsilon_M)$. In other words, for any lifetime $\zeta \in \set{U}$, $M^p(t_s)$ represents the number of tasks \emph{encountered} after \emph{searching} for $t_s$ time. We call the encounter rate for this process \termdef{Boft.01}{lambda}{$\lambda$}{Merged \aimention{Sim\'{e}on-Denis Poisson}Poisson encounter rate for all tasks (tasks per second)}, where $\lambda = \sum_{i=1}^n \lambda_i$ by the theory of \index{stochasticity!Poisson process!merged}merged \aimention{Sim\'{e}on-Denis Poisson}Poisson processes \citep{Viniotis98}. Therefore, $\E(\Upsilon_1)=1/\lambda$. Because this process is also a \aimention{Andrei A. Markov}Markov renewal process, $\aslim_{t_s \to \infty} M(t_s) = \infty$; however, because this is a \aimention{Sim\'{e}on-Denis Poisson}Poisson counting process, $\E(M(t_s))=\lambda t_s$ for all $t_s \in \R_{\geq0}$.% \index{solitary agent model!classical analysis!Poisson encounters|)indexdef} \subsubsection{Merged Task-Type Processes}% \index{solitary agent model!classical analysis!reward processes|(indexdef} Define the random processes $(\Game_M)$, $(\mho_M)$, $(\daleth_M)$, and $(I_M)$ as merged versions of the families $((G^i_M))_{i=1}^n$, $((C^i_M))_{i=1}^n$, $((T^i_M))_{i=1}^n$, and $((I^i_M))_{i=1}^n$ respectively. Each of these processes is an \iid{}\ sequence of random variables. The random variables $I_1$ and $\Upsilon_1$ are assumed to be independent. For any lifetime $\zeta \in \set{U}$, $I_1=i$ would indicate that the first encounter was generated by process $(M_i(t_s): t_s \in \R_{\geq0})$. It will be convenient for us to introduce the symbols \termdef{Boft.0510}{oftg}{$g$}{Gross gain random variable for processing a task during one \ac{OFT} \aimention{Andrei A. Markov}Markov renewal cycle (points)}, \termdef{Boft.0520}{oftc}{$c$}{Cost random variable for processing a task during one \ac{OFT} \aimention{Andrei A. Markov}Markov renewal cycle (points)}, and \termdef{Boft.0530}{ofttau}{$\tau$}{Time random variable for processing a task during one \ac{OFT} \aimention{Andrei A. Markov}Markov renewal cycle (seconds)} defined by % \begin{equation*} g \triangleq \E\left(\Game_1\right) \quad \text{ and } \quad c \triangleq \E\left(\mho_1\right) \quad \text{ and } \quad \tau \triangleq \E\left(\daleth_1\right) \end{equation*} % These random variables respectively represent the net gain, cost, and time for processing a task during a single arbitrary \ac{OFT} renewal cycle. % \index{solitary agent model!classical analysis!reward processes|)indexdef}% \index{solitary agent model!classical analysis!statistics|(indexdef}% We also use the notation \termdef{Boft.0511}{oftavgg}{$\overline{g}$}{Expected gross gain for processing a task during one \ac{OFT} \aimention{Andrei A. Markov}Markov renewal cycle (points)}, \termdef{Boft.0521}{oftavgc}{$\overline{c}$}{Expected cost for processing a task during one \ac{OFT} \aimention{Andrei A. Markov}Markov renewal cycle (points)}, and \termdef{Boft.0531}{oftavgtau}{$\overline{\tau}$}{Expected time for processing a task during one \ac{OFT} \aimention{Andrei A. Markov}Markov renewal cycle (seconds)} defined by % \begin{equation*} \overline{g} \triangleq \E\left(g\right) = \E\left( \Game_1 \right) \quad \text{ and } \quad \overline{c} \triangleq \E\left(c\right) = \E\left( \mho_1 \right) \quad \text{ and } \quad \overline{\tau} \triangleq \E\left(\tau\right) = \E\left( \daleth_1 \right) \end{equation*} % From the theory of \index{stochasticity!Poisson process!merged}merged \aimention{Sim\'{e}on-Denis Poisson}Poisson processes, $\Pr( I_1 = i ) = \lambda_i/\lambda$ for all $i \in \{1,2,\dots,n\}$. Combining this with the fact that $\lambda = \sum_{i=1}^n \lambda_i$ and a property\footnote{For random variables $X$ and $Y$, $\E(X)=\E(\E(X|Y))$.} of expectation yields % \begin{equation*} \overline{g} = \sum\limits_{j=1}^n \frac{\lambda_j}{\lambda} p_j g_j \quad \text{ and } \quad \overline{c} = \sum\limits_{j=1}^n \frac{\lambda_j}{\lambda} p_j c_j \tau_j \quad \text{ and } \quad \overline{\tau} = \sum\limits_{j=1}^n \frac{\lambda_j}{\lambda} p_j \tau_j \end{equation*} % So, these expectations are weighted sums of parameters. In particular, if $n = 1$, % \begin{equation*} \overline{g} = p_1 g_1(\tau_1) \quad \text{ and } \quad \overline{c} = p_1 c_1 \tau_1 \quad \text{ and } \quad \overline{\tau} = p_1 \tau_1 \end{equation*} % This result is useful when visualizing optimization results. Additionally, % \begin{equation*} \E\left( C^s \Upsilon_1 | I_1 = i \right) = \E\left( C^s \Upsilon_1 \right) = \frac{c^s}{\lambda} \end{equation*} % Below, we use these results frequently in expressions of statistics. \index{solitary agent model!classical analysis!statistics|)indexdef}% %%fakeparagraph{Partial Derivatives:} %\paragraph{Partial Derivatives:} In \longref{ch:optimization_results}, %it will be useful to take partial derivatives with respect to the %preference probabilities and processing times. For all $i \in %\{1,2,\dots,n\}$, %% %\begin{equation*} % \frac{ \partial \lambda }{ \partial p_i } = % \frac{ \partial^2 \lambda }{ {\partial p_i}^2 } = % \frac{ \partial \lambda }{ \partial \tau_i } = % \frac{ \partial^2 \lambda }{ {\partial \tau_i}^2 } = % 0 %\end{equation*} %% %and %% %\begin{equation*} % \frac{ \partial \overline{g} }{ \partial p_i } % = % \frac{\lambda_i}{\lambda} g_i % \quad \text{ and } \quad % \frac{ \partial \overline{c} }{ \partial p_i } % = % \frac{\lambda_i}{\lambda} c_i \tau_i % \quad \text{ and } \quad % \frac{ \partial \overline{\tau} }{ \partial p_i } % = % \frac{\lambda_i}{\lambda} \tau_i %\end{equation*} %% %and %% %\begin{equation*} % \frac{ \partial \overline{g} }{ \partial \tau_i } % = % \frac{\lambda_i}{\lambda} p_i g_i'(\tau_i) % \quad \text{ and } \quad % \frac{ \partial \overline{c} }{ \partial \tau_i } % = % \frac{\lambda_i}{\lambda} p_i c_i % \quad \text{ and } \quad % \frac{ \partial \overline{\tau} }{ \partial \tau_i } % = % \frac{\lambda_i}{\lambda} p_i %\end{equation*} %% %Thus, %% %\begin{equation} % \lambda \frac{ \partial \overline{g} }{ \partial p_i } % = \lambda_i g_i % \quad \text{ and } \quad % \lambda \frac{ \partial \overline{c} }{ \partial p_i } % = \lambda_i c_i \tau_i % \quad \text{ and } \quad % \lambda \frac{ \partial \overline{\tau} }{ \partial p_i } % = \lambda_i \tau_i % \label{eq:oft_partial_p} %\end{equation} %% %and %% %\begin{equation} % \lambda \frac{ \partial \overline{g} }{ \partial \tau_i } % = \lambda_i p_i g_i'(\tau_i) % \quad \text{ and } \quad % \lambda \frac{ \partial \overline{c} }{ \partial \tau_i } % = \lambda_i p_i c_i % \quad \text{ and } \quad % \lambda \frac{ \partial \overline{\tau} }{ \partial \tau_i } % = \lambda_i p_i % \label{eq:oft_partial_tau} %\end{equation} %% %where $g_i'(\tau_i)$ is the first derivative of the $g_i(\tau_i)$ %parameter function. \subsubsection{Net Gain, Cost, and Time Processes} \index{solitary agent model!classical analysis!reward processes|(indexdef}% Now, we define random processes \termdef[$(\oft{G}_N)$]{Boft.11}{oftG1}{$\oft{G}_1$}{Net gain from a single \ac{OFT} renewal cycle (points)}, \termdef[$(\oft{C}_N)$]{Boft.12}{oftC1}{$\oft{C}_1$}{Cost from a single \ac{OFT} renewal cycle (points)}, and \termdef[$(\oft{T}_N)$]{Boft.13}{oftT1}{$\oft{T}_1$}{Length of time of a single \ac{OFT} renewal cycle (seconds)} with % \begin{equation*} \oft{G}_N \triangleq \Game_N - \mho_N - C^s \Upsilon_N \quad \text{ and } \quad \oft{C}_N \triangleq \mho_N + C^s \Upsilon_N \quad \text{ and } \quad \oft{T}_N \triangleq \daleth_N + \Upsilon_N \end{equation*} % for all $N \in \N$ and $\zeta \in \set{U}$. It is clear that $(\oft{G}_N)$, $(\oft{C}_N)$, and $(\oft{T}_N)$ are \iid{}\ sequences of random variables with finite expectation. In some cases, it will be interesting to look at the \emph{gross gain} returned to an agent. Thus, we define the process $(\oft{G}_N+\oft{C}_N)$ as well\footnote{Recall that the all cost rates may be negative in this model. While these costs would be interpreted as gains in this case, they are not included in this definition of gross gain. Gross gain is all gains before the impact of costs, positive or negative.}. By the above definitions, $\oft{G}_1 + \oft{C}_1 = g$ and $\oft{G}_N + \oft{C}_N = \Game_N$ for all $N \in \N$ and $\zeta \in \set{U}$. % \index{solitary agent model!classical analysis!reward processes|)indexdef}% \index{solitary agent model!classical analysis!statistics|(indexdef}% The statistics of these random variables are of interest to us. In particular, %\termdef[]{Boft.21}{oftEG1}{$\E(\oft{G}_1)$}{Expected net gain from a %single \ac{OFT} renewal cycle (points)} %\termdef[]{Boft.22}{oftEC1}{$\E(\oft{C}_1)$}{Expected cost from a %single \ac{OFT} renewal cycle %(points)}\termdef[]{Boft.23}{oftET1}{$\E(\oft{T}_1)$}{Expected length %of time of a single \ac{OFT} renewal %cycle (seconds)} \begin{align} \E\left( \oft{G}_1 \right) &= \overline{g} - \overline{c} - \frac{c^s}{\lambda} \label{eq:oft_EG1} \\ \E\left( \oft{C}_1 \right) &= \overline{c} + \frac{c^s}{\lambda} \label{eq:oft_EC1} \\ \E\left( \oft{T}_1 \right) &= \overline{\tau} + \frac{1}{\lambda} \label{eq:oft_ET1} \\ \E\left( \oft{G}_1 + \oft{C}_1 \right) &= \overline{g} \label{eq:oft_EGC1} \end{align} % Also, $\Pr( \oft{T}_1 = 0 ) = 0$ because $\E(\oft{T}_1) > 0$ and $\Pr( \Upsilon_1 = 0 ) = 0$ \index{solitary agent model!classical analysis!statistics|)indexdef}% \subsection{Markov Renewal Process}% \label{sec:oft_model_markov_renewal_process}% \aimention{Andrei A. Markov}% \index{stochasticity!Markov renewal process|(}% \index{solitary agent model!classical analysis!renewal process|(indexdef}% Because $(\oft{T}_N)$ is an \iid{}\ sequence of random variables with $0 < \E(\oft{T}_1) < \infty$ and $\Pr( \oft{T}_1 ) = 0$, the process \termdef[$(N(t): t \in \R_{\geq0})$]{Boft.02}{oftNt}{$N(t)$}{Number of tasks encountered after $t$ seconds} defined by % \begin{equation*} N(t) \triangleq \sup \left\{ N \in \N : \sum\limits_{i=1}^N \oft{T}_i \leq t \right\} = \sup \left\{ N \in \N : \sum\limits_{i=1}^N \left( \daleth_i + \Upsilon_i \right) \leq t \right\} \end{equation*} % for all $t \in \R_{\geq0}$ and all $\zeta \in \set{U}$ is a \aimention{Andrei A. Markov}Markov renewal process with interarrival process $(\oft{T}_N)$. This process represents the number of tasks \emph{encountered} from time $0$ to time $t$ (\ie, $t$ is a measure of the agent's lifetime, not how long the agent has searched). This \aimention{Andrei A. Markov}Markov renewal process is depicted in \longref{fig:oft_markov_process}, and one iteration around this process will be known as an \index{Markov renewal cycles!OFT cycle|see{solitary agent model, classical analysis, OFT cycle}}\index{OFT cycle|see{solitary agent model, classical analysis, OFT cycle}}\index{solitary agent model!classical analysis!OFT cycle|indexdef}\emph{\ac{OFT} cycle}. % %\begin{figure}[!ht]\centering \begin{figure}\centering \begin{picture}(265,42)(0,0) \thinlines \put(0,25){\vector(1,0){50}} \put(53,25){\makebox(0,0)[l]{Search}} \put(90,25){\vector(1,0){15}} \put(107,25){\makebox(0,0)[l]{Encounter}} \put(163,25){\line(1,0){20}} % \put(183,25){\vector(2,1){24}} \put(210,37){\makebox(0,0)[l]{Process}} \put(250,37){\line(1,0){15}} % \put(183,25){\vector(2,-1){24}} \put(210,13){\makebox(0,0)[l]{Ignore}} \put(250,13){\line(1,0){15}} % \put(265,37){\line(0,-1){37}} \put(265,0){\line(-1,0){265}} \put(0,0){\line(0,1){25}} % \put(47.5,33){\circle*{5}} \end{picture} \caption[Classical OFT Markov Renewal Process]{The classical \ac{OFT} \aimention{Andrei A. Markov}Markov renewal process, where the solid dot is the renewal point that starts each \index{solitary agent model!classical analysis!OFT cycle}cycle.} \label{fig:oft_markov_process} \end{figure} % That is, because the agent can choose to process or ignore a task, the holding time for the renewal process always includes some search time and may include processing time if an encounter is followed by a decision to process the task. By definition of this process, simultaneous encounters occur with probability zero. As with any \aimention{Andrei A. Markov}Markov renewal process, $\aslim_{t \to \infty} N(t) = \infty$; however, while $\E(M(t_s))$ is known for all $t_s \in \R_{\geq0}$, a derivation of $\E(N(t))$ for all $t \in \R_{\geq0}$ is outside the scope of this work. Fortunately, applications rarely require the precise form of this expectation. Additionally, it is known that for all $\zeta \in \set{U}$ and all $t \in \R_{\geq0}$, $N(t) \leq M(t)$; therefore, $0 \leq \E( N(t) ) \leq \lambda t$ for all $t \in \R_{\geq0}$.% \subsubsection{Encounter Times: Statistics and Stochastic Limits} The process \termdef[$(\oft{T}^N)$]{Boft.33}{oftTN}{$\oft{T}^N$}{Total length of time for $N$ \index{Markov renewal cycle"!OFT cycle"|indexglo}\ac{OFT} \aimention{Andrei A. Markov}Markov renewal cycles (seconds)} defined with $\oft{T}^N \triangleq \sum_{i=1}^N \oft{T}_i$ for all $N \in \N$ and all $\zeta \in \set{U}$ is the sequence of encounter times for $(N(t):t \in \R_{\geq0})$. Because $(\oft{T}_N)$ is an \iid{}\ sequence of random variables with finite expectation, %\termdef[]{Boft.43}{oftETN}{$\E(\oft{T}^N)$}{Expected total length of %time for $N$ \index{Markov renewal cycle"!OFT cycle"|indexglo}\ac{OFT} %\aimention{Andrei A. Markov}Markov renewal cycles (seconds)} % \begin{equation*} \E\left( \oft{T}^N \right) = N \E\left( \oft{T}_1 \right) = \frac{N}{\lambda} + N \overline{\tau} \end{equation*} % for all $N \in \N$. It can be shown\footnote{See \longref{app:markov_renewal_sto_limits}.} that % \begin{equation} \aslim\limits_{t \to \infty} \frac{ N(t) }{t} = \lim\limits_{t \to \infty} \frac{ \E\left( N(t) \right) }{t} = \aslim\limits_{N \to \infty} \frac{ N }{ \oft{T}^N } = \lim\limits_{N \to \infty} \E\left( \frac{ N }{ \oft{T}^N } \right) = \frac{1}{ \E\left(\oft{T}_1\right) } \label{eq:oft_long_rate} \end{equation} % Therefore, the ratio $1/\E(\oft{T}_1)$ may be called the \emph{long-term encounter rate} of $(N(t):t \in \R_{\geq0})$. Similarly, it is also the case that % \begin{equation*} \aslim\limits_{t \to \infty} \frac{ \oft{T}(t) }{t} = \lim\limits_{t \to \infty} \frac{ \E\left( \oft{T}(t) \right) }{t} = 1 \end{equation*} % which is not surprising; that is, as the agent's lifetime increases, the time spent waiting for the very next task encounter becomes negligible.% \index{solitary agent model!classical analysis!renewal process|)indexdef}% \index{stochasticity!Markov renewal process|)} \subsection{Markov Renewal-Reward Processes} \label{sec:oft_markov_renewal_reward_processes}% \aimention{Andrei A. Markov}% \index{stochasticity!Markov renewal-reward process|(}% \index{solitary agent model!classical analysis!reward processes|(indexdef} The processes $(\oft{G}_N)$ and $(\oft{C}_N)$ can be viewed as sequences of gains and losses, respectively, corresponding to each $(N(t):t \in \R_{\geq0})$ encounter. Define the corresponding cumulative processes\footnote{A \emph{cumulative process} is a sequence of partial sums of another process.} \termdef[$(\oft{G}^N)$]{Boft.31}{oftGN}{$\oft{G}^N$}{Total net gain for $N$ OFT \aimention{Andrei A. Markov}Markov renewal cycles (points)}, \termdef[$(\oft{C}^N)$]{Boft.32}{oftCN}{$\oft{C}^N$}{Total cost for $N$ OFT \aimention{Andrei A. Markov}Markov renewal cycles (points)}, and $(\oft{G}^N+\oft{C}^N)$ with % \begin{equation*} \oft{G}^N \triangleq \sum\limits_{i=1}^N \oft{G}_i \quad \text{ and } \quad \oft{C}^N \triangleq \sum\limits_{i=1}^N \oft{C}_i \quad \text{ and } \quad \oft{G}^N + \oft{C}^N = \sum\limits_{i=1}^N \left( \oft{G}_i + \oft{C}_i \right) \end{equation*} % for all $N \in \N$ and all $\zeta \in \set{U}$. Also define the \aimention{Andrei A. Markov}Markov renewal-reward processes\footnote{A \emph{\aimention{Andrei A. Markov}Markov renewal-reward process} uses a \aimention{Andrei A. Markov}Markov renewal process to extend the indexing of a cumulative process from $\N$ to $\R_{\geq0}$.} \termdef[$(\oft{G}(t): t \in \R_{\geq0})$]{Boft.51}{oftGt}{$\oft{G}(t)$}{Total net gain after $t$ seconds (\ie, $\oft{G}^{N(t)}$) (points)}, \termdef[$(\oft{C}(t): t \in \R_{\geq0})$]{Boft.52}{oftCt}{$\oft{C}(t)$}{Total cost after $t$ seconds (\ie, $\oft{C}^{N(t)}$) (points)}, and \termdef[$(\oft{T}(t): t \in \R_{\geq0})$]{Boft.53}{oftTt}{$\oft{T}(t)$}{Total length of time after $t$ seconds for all completed OFT \aimention{Andrei A. Markov}Markov renewal cycles (\ie, $\oft{T}^{N(t)}$) (seconds)} with % \begin{equation*} \oft{G}(t) \triangleq \oft{G}^{N(t)} = \sum\limits_{i=1}^{N(t)} \oft{G}_i \enskip \text{ and } \enskip \oft{C}(t) \triangleq \oft{C}^{N(t)} = \sum\limits_{i=1}^{N(t)} \oft{C}_i \enskip \text{ and } \enskip \oft{T}(t) \triangleq \oft{T}^{N(t)} = \sum\limits_{i=1}^{N(t)} \oft{T}_i \end{equation*} % and the process $(\oft{G}(t) + \oft(C)(t):t \in \R_{\geq0})$ accordingly with % \begin{equation*} \oft{G}(t) + \oft{C}(t) = \oft{G}^{N(t)} + \oft{C}^{N(t)} = \sum\limits_{i=1}^{N(t)} \left( \oft{G}_i + \oft{C}_i \right) \end{equation*} % for all $t \in \R_{\geq0}$ and $\zeta \in \set{U}$.% \index{stochasticity!Markov renewal-reward process|)} \index{solitary agent model!classical analysis!reward processes|)indexdef}% \subsection{Reward Process Statistics}% \label{sec:oft_reward_process_stats}% \index{solitary agent model!classical analysis!statistics|(indexdef} Because $(\oft{G}_N)$ and $(\oft{C}_N)$ are \iid{}\ sequences of random variables with finite expectation, for all $N \in \N$, %\termdef[]{Boft.41}{oftEGN}{$\E(\oft{G}^N)$}{Expected total net gain %for $N$ OFT \aimention{Andrei A. Markov}Markov renewal cycles %(points)}\termdef[]{Boft.42}{oftECN}{$\E(\oft{C}^N)$}{Expected total %cost for $N$ OFT \aimention{Andrei A. Markov}Markov renewal cycles %(points)} % \begin{align} \E\left( \oft{G}^N \right) &= N \E\left( \oft{G}_1 \right) = N \left( \overline{g} - \overline{c} %\sum\limits_{i=1}^n \frac{\lambda_i}{\lambda} %\left( p_i ( g_i - c_i \tau_i ) \right) - \frac{c^s}{\lambda} \right) \label{eq:oft_EGN} \\ \E\left( \oft{C}^N \right) &= N \E\left( \oft{C}_1 \right) = N \left( \overline{c} %\sum\limits_{i=1}^n \frac{\lambda_i}{\lambda} p_i c_i \tau_i + \frac{c^s}{\lambda} \right) \label{eq:oft_ECN} \\ % \intertext{and, as we showed above,} % \E\left( \oft{T}^N \right) &= N \E\left( \oft{T}_1 \right) = N \left( \frac{1}{\lambda} + \overline{\tau} %\sum\limits_{i=1}^n \frac{\lambda_i}{\lambda} p_i \tau_i \right) \label{eq:oft_ETN} \end{align} % It is clearly the case that % \begin{equation} \E\left( \oft{G}^N + \oft{C}^N \right) = N \E\left( \oft{G}_1 + \oft{C}_1 \right) = N \overline{g} \label{eq:oft_EGCN} \end{equation} % Also, for all $t \in \R_{\geq0}$,%\termdef[]{Boft.61}{oftEGt}{$\E(\oft{G}(t))$}{Expected %total net gain after $t$ seconds %(points)}\termdef[]{Boft.62}{oftECt}{$\E(\oft{C}(t))$}{Expected cost %after $t$ seconds %(points)}\termdef[]{Boft.63}{oftETt}{$\E(\oft{T}(t))$}{Expected total %length of time after $t$ seconds of all completed OFT \aimention{Andrei %A. Markov}Markov renewal cycles (seconds)} % \begin{align} \E\left( \oft{G}(t) \right) &= \E\left( N(t) \right) \E\left( \oft{G}_1 \right) = \E\left( N(t) \right) \left( \overline{g} - \overline{c} - \frac{c^s}{\lambda} \right) \label{eq:oft_EGt} \\ \E\left( \oft{C}(t) \right) &= \E\left( N(t) \right) \E\left( \oft{C}_1 \right) = \E\left( N(t) \right) \left( \overline{c} + \frac{c^s}{\lambda} \right) \label{eq:oft_ECt} \\ \E\left( \oft{T}(t) \right) &= \E\left( N(t) \right) \E\left( \oft{T}_1 \right) = \E\left(N(t)\right) \left( \frac{1}{\lambda} + \overline{\tau} \right) \label{eq:oft_ETt} \end{align} % and, clearly, % \begin{equation} \E\left( \oft{G}(t) + \oft{C}(t) \right) = \E\left( N(t) \right) \E\left( \oft{G}_1 + \oft{C}_1 \right) = \E\left( N(t) \right) \overline{g} \label{eq:oft_EGCt} \end{equation} \index{solitary agent model!classical analysis!statistics|)indexdef} \subsubsection{Stochastic Limits of Net Gain Processes}% \index{solitary agent model!classical analysis!limits|(indexdef} It can be shown\footnote{See \longref{app:markov_renewal_sto_limits}.} that there exists an $N \in \N$ such that $\E( 1 / \oft{T}^N ) < \infty$, and so by results of \citet{JohnsMiller63}, % \begin{equation} \aslim\limits_{t \to \infty} \frac{ \oft{G}(t) }{t} = \lim\limits_{t \to \infty} \frac{ \E\left( \oft{G}(t) \right) }{t} = \aslim\limits_{N \to \infty} \frac{ \oft{G}^N }{ \oft{T}^N } = \lim\limits_{N \to \infty} \E\left( \frac{ \oft{G}^N }{ \oft{T}^N } \right) = \frac{ \E\left(\oft{G}_1\right) }{ \E\left(\oft{T}_1\right) } \label{eq:oft_payoff_long_rate} \end{equation} % This result is frequently used in classical \ac{OFT}. The ratio $\E(G_1)/\E(T_1)$ may be called the \index{long-term average rate of net gain|(indexdef}\emph{long-term (average) rate of net gain} and is expressed by % \begin{equation*} \frac{ \E\left(\oft{G}_1\right) }{ \E\left(\oft{T}_1\right) } = \frac { \overline{g} - \overline{c} - \frac{c^s}{\lambda} } { \frac{1}{\lambda} + \overline{\tau} } = \frac { \lambda\left( \overline{g} - \overline{c} \right) - c^s } { 1 + \lambda \overline{\tau} } = \frac { \sum\limits_{i=1}^n \lambda_i p_i ( g_i - c_i \tau_i ) - c^s } { 1 + \sum\limits_{i=1}^n \lambda_i p_i \tau_i } \end{equation*} % \index{long-term average rate of net gain|)indexdef}% So, % \begin{equation} \frac{ \E\left(\oft{G}_1\right) }{ \E\left(\oft{T}_1\right) } = \frac{ \E\left(\oft{G}^N\right) }{ \E\left(\oft{T}^N\right) } = \frac{\E\left(\oft{G}(t)\right)}{ \E\left(\oft{T}(t)\right) } \label{eq:oft_payoff_long_rate_equiv} \end{equation} % for all $N \in \N$ and $t \in \R_{>0}$.% \index{solitary agent model!classical analysis!limits|)indexdef} \subsubsection{Variance Under Pseudo-Deterministic Conditions}% \index{solitary agent model!classical analysis!variance|(indexdef}% \index{solitary agent model!classical analysis!statistics|(indexdef} The statistics of the processes $(\oft{G}^N)$, $(\oft{C}^N)$, $(\oft{T}^N)$, and $(\oft{G}^N + \oft{C}^N)$ are of particular interest to us. The expectation of the random variables in these processes are given in \longrefs{eq:oft_EGN}, \shortref{eq:oft_ECN}, \shortref{eq:oft_ETN}, and \shortref{eq:oft_EGCN}, respectively; however, it is useful to know their \index{variance|see{stochasticity, statistics, variance}}variances% \footnote{\index{stochasticity!statistics!variance ($\var$)|(indexdef}For a random variable $X$, the variance $\var(X)$ is $\E( (X - \E(X))^2 )$, which is equivalent to $\E(X^2) - \E(X)^2$. Variance is sometimes called the \emph{second \index{central moments|see{stochasticity, statistics, central moments}}\index{stochasticity!statistics!central moments|indexdef}central moment} because it integrates the squared differences from the mean (\ie, the center of the distribution). This is a measure of the likely variability of outcomes.\index{stochasticity!statistics!variance ($\var$)|)indexdef}} as well, especially when considering risk. Because these four processes are collections of \iid{}\ random variables, %\termdef[]{Boft.411}{oftvarGN}{$\var(\oft{G}^N)$}{Variance in total net %gain for $N$ OFT \aimention{Andrei A. Markov}Markov renewal cycles %(points${}^2$)}\termdef[]{Boft.421}{oftvarCN}{$\var(\oft{C}^N)$}% %{Variance in total cost for $N$ OFT \aimention{Andrei A. Markov}Markov %renewal cycles %(points${}^2$)}\termdef[]{Boft.431}{oftvarTN}{$\var(\oft{T}^N)$}% %{Variance in total length of time for $N$ OFT \aimention{Andrei A. %Markov}Markov renewal cycles (seconds${}^2$)} % \begin{align*} \var\left( \oft{G}^N \right) &= N \var\left( \oft{G}_1 \right) = N \left( \var\left(\Game_1 - \mho_1\right) + \var\left(C^s \Upsilon_1\right) \right) \\ \var\left( \oft{C}^N \right) &= N \var\left( \oft{C}_1 \right) = N \left( \var\left( \mho_1 \right) + \var\left( C^s \Upsilon_1 \right) \right) \\ \var\left( \oft{T}^N \right) &= N \var\left( \oft{T}_1 \right) = N \left( \var\left( \Upsilon_1 \right) + \var\left( C^s \Upsilon_1 \right) \right) \\ \var\left( \oft{G}^N + \oft{C}^N \right) &= N \var\left( \oft{G}_1 + \oft{C}_1 \right) = N \var\left( \Game_1 \right) \end{align*} % for all $N \in \N$. However, the derivations of the variances of $\oft{G}_1$, $\oft{C}_1$, $\oft{T}_1$, and $\oft{G}_1 + \oft{C}_1$ are difficult in general. Additionally, they require us to introduce parameters representing the variance of the random variables $g^i_1$, $c^i_1$ and $\tau^i_1$ for all $i \in \{1,2,\dots,n\}$, which may not be known in applications. Thus, we focus on one particular simplified case; for all $i \in \{1,2,\dots,n\}$, we assume that \index{stochasticity!random variable!pseudo-deterministic}% % \begin{equation*} \Pr( g^i_1 = g_i ) = \Pr( c^i_1 = c_i ) = \Pr( \tau^i_i = \tau_i ) = 1 \end{equation*} % This roughly means that the gains, cost rates, and processing times for tasks of any particular type are all deterministic. We also make use of the following assumptions. % \begin{enumerate}[(i)] \item For all $i \in \{1,2,\dots,n\}$, $X^i_1$ is uncorrelated with each of of $(g^i_1 - c^i_1 \tau^i_1)^2$, $(c^i_1 \tau^i_1)^2$, and $(\tau^i_1)^2$. \item For all $i \in \{1,2,\dots,n\}$, $g^i_1$ is uncorrelated with $c^i_1 \tau^i_1$. \item $\Game_1 - \mho_1$ is uncorrelated with $C^s \Upsilon_1$. \item $(C^s)^2$ is uncorrelated with $(\Upsilon_1)^2$. \item $(C^s \Upsilon_1)^2$ is independent of $I_1$. \end{enumerate} % From these assumptions, we derive the second moments % \begin{align} \E\left( g^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda_i}{\lambda} p_i \left( g_i \right)^2 \label{eq:oft_cycle_proc_gross_gain_2moment} \\ % \E\left( c^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda_i}{\lambda} p_i \left( c_i \tau_i \right)^2 \label{eq:oft_cycle_proc_cost_2moment} \\ % \E\left( \tau^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda_i}{\lambda} p_i \left( \tau_i \right)^2 \label{eq:oft_cycle_proc_time_2moment} \\ % \E\left( \left(g - c\right)^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda_i}{\lambda} p_i \left( g_i - c_i \tau_i \right)^2 \label{eq:oft_cycle_net_gain_2moment} \end{align} % which can be used to derive other second moments and variances. So, for all $N \in \N$, % \begin{align} \E\left( \oft{G}_1^2 \right) &= \E\left( \left(g - c\right)^2 \right) - 2 \frac{c^s}{\lambda} \E\left( \oft{G}_1 \right) \label{eq:oft_net_gain_2moment} \\ \E\left( \oft{C}_1^2 \right) &= \E\left( c^2 \right) - 2 \frac{c^s}{\lambda} \E\left( \oft{C}_1 \right) \label{eq:oft_cost_2moment} \\ \E\left( \oft{T}_1^2 \right) &= \E\left( \tau^2 \right) - 2 \frac{1}{\lambda} \E\left( \oft{T}_1 \right) \label{eq:oft_time_2moment} \\ \E\left( \left( \oft{G}_1 + \oft{C}_1 \right)^2 \right) &= \E\left( g^2 \right) \label{eq:oft_gross_gain_2moment} \end{align} % and % \begin{align} \var\left( \oft{G}^N \right) &= N \left( \var\left( g - c \right) + \left( \frac{c^s}{\lambda} \right)^2 \right) \label{eq:oft_net_gain_variance} \\ \var\left( \oft{C}^N \right) &= N \left( \var\left( c \right) + \left( \frac{c^s}{\lambda} \right)^2 \right) \label{eq:oft_cost_variance} \\ \var\left( \oft{T}^N \right) &= N \left( \var\left( \tau \right) + \left( \frac{1}{\lambda} \right)^2 \right) \label{eq:oft_time_variance} \\ \var\left( \oft{G}^N + \oft{C}^N \right) &= N \var\left( g \right) \label{eq:oft_gross_gain_variance} \end{align} % Under these assumptions, the only variance in the model comes from the varying time spent searching for tasks and the uncertainty in the type of task encountered.% \index{solitary agent model!classical analysis!statistics|)indexdef}% \index{solitary agent model!classical analysis!variance|)indexdef}% \index{solitary agent model!classical analysis|)indexdef}% \index{optimal foraging theory|)} \section{Finite Lifetime Analysis: Processing-Based Approach} \label{sec:processing_only_model} \index{solitary agent model!processing-only analysis|(indexdef}% Recall that the agent suffers no recognition cost upon an encounter with a task. Therefore, it makes sense to exclude tasks that are ignored (\ie, not chosen for processing) from the model entirely by adjusting the encounter rate for each task type. This adjustment is possible in our model specifically because encounters are generated by \aimention{Sim\'{e}on-Denis Poisson}Poisson processes. Thus, in our approach, we \index{split Poisson process|see{stochasticity, Poisson process, split}}\index{stochasticity!Poisson process!split}split the task-type processes immediately to thin them of their ignored tasks. We then merge these $n$ thinned processes to form a \index{stochasticity!Poisson process!merged}merged process generated by only the task encounters that result in processing. We can then proceed in the same way as the classical \ac{OFT} approach, except we assume the agent processes every task from this \index{stochasticity!Poisson process!merged}merged process. Thus, we call this a \index{split before merge approach}\emph{split before merge} approach. This approach differs from the classical \ac{OFT} approach which splits based on processing \emph{after} merging the task-type processes. Because the approach proceeds in an identical way as classical \ac{OFT} after these modifications, most of this section provides results without a great deal of justification. \subsection{Poisson Encounters of Processed Tasks of One Type}% \aimention{Sim\'{e}on-Denis Poisson} \index{solitary agent model!processing-only analysis!Poisson encounters|(indexdef}% For all $i \in \{1,2,\dots,n\}$, define $(M^p_i(t_s):t_s \in \R_{\geq0})$ and \termdef[$\lambda_i^p \in \R_{>0}$]% {Cprocess.001}{lambdapi}{$\lambda^p_i$}{\aimention{Sim\'{e}on-Denis Poisson}Poisson encounter rate with processed tasks of type $i$ (processed tasks per second)}, % \begin{equation*} M^p_i(t_s) \triangleq \sum\limits_{i=1}^{M_i(t_s)} X_i \quad \text{ and } \quad \lambda^p_i \triangleq p_i \lambda_i \end{equation*} % for all $t_s \in \R_{\geq0}$ and $\zeta \in \set{U}$. Also define $\set{G}^p$ with $\set{G}^p \triangleq \{ i \in \{1,2,\dots,n\} : p_i > 0 \}$. Roughly speaking, for all $\zeta \in \set{U}$, $M^p_i(t_s)$ is a version of $M_i(t_s)$ with all task encounters that do not result in processing removed; that is, $M^p_i(t_s)$ is the number of tasks \emph{processed} after \emph{searching} for $t_s$ time. For all $i \in \set{G}^p$, $(M^p_i(t_s):t_s \in \R_{\geq0})$ is a \index{stochasticity!Poisson process!split}split \aimention{Sim\'{e}on-Denis Poisson}Poisson process with rate $\lambda^p_i$.% \index{solitary agent model!processing-only analysis!Poisson encounters|)indexdef}% \index{solitary agent model!processing-only analysis!reward processes|(indexdef}% Therefore, for all $i \in \set{G}^p$, define $(\hat{G}^i_M)$, $(\hat{C}^i_M)$, $(\hat{T}^i_M)$, and $(\hat{I}^i_M)$ as thinned versions of $(G^i_M)$, $(C^i_M)$, $(T^i_M)$, and $(I^i_M)$ respectively. For all $i \in \{1,2,\dots,n\}$ with $i \notin \set{G}^p$, define $\hat{G}^i_M = \hat{C}^i_M = \hat{T}^i_M = 0$ and $\hat{I}^i_M = i$ for all $M \in \N$. Now we may proceed in an identical way as classical \ac{OFT} using these thinned processes; however, because the $p_i$ parameter has been absorbed into $\lambda_i^p$, it can be omitted.% \index{solitary agent model!processing-only analysis!reward processes|)indexdef}% \subsubsection{Poisson Encounters of All Processed Tasks}% \aimention{Sim\'{e}on-Denis Poisson}% \index{solitary agent model!processing-only analysis!Poisson encounters|(indexdef} Assume that $\set{G}^p \neq \emptyset$. This assumption follows from the requirement that an agent must process some finite number of tasks in its lifetime. Define $(M^p(t_s):t_s \in \R_{\geq0})$ and \termdef[$\lambda^p \in \R_{>0}$]{Cprocess.01}{lambdap}{$\lambda^p$}{\aimention{Sim\'{e}on-Denis Poisson}Poisson encounter rate with processed tasks of all types (processed tasks per second)} with % \begin{equation*} M^p(t_s) \triangleq \sum\limits_{i \in \set{G}^p} M^p_i(t_s) = \sum\limits_{i=1}^n M^p_i(t_s) \quad \text{ and } \quad \lambda^p \triangleq \sum\limits_{i \in \set{G}^p} \lambda^p_i = \sum\limits_{i=1}^n \lambda^p_i \end{equation*} % for all $t_s \in \R_{\geq0}$ and all $\zeta \in \set{U}$. $(M^p(t_s):t_s \in \R_{\geq0})$ is a \index{stochasticity!Poisson process!merged}merged \aimention{Sim\'{e}on-Denis Poisson}Poisson process with rate $\lambda^p$. The process is generated only by encounters that lead to processing. That is, for all $\zeta \in \set{U}$, $M^p(t_s)$ is the \emph{total} number of tasks \emph{processed} after \emph{searching} for $t_s$ time. Call the interevent time process for this task $(\Upsilon^p_m)$. Therefore, $\E(\Upsilon^p_1) = 1/\lambda^p$, $\aslim_{t_s \to \infty} M^p(t_s) = \infty$, and $\E(M^p(t_s)) = \lambda^p t_s$ for all $t_s \in \R_{\geq0}$.% \index{solitary agent model!processing-only analysis!Poisson encounters|)indexdef} \subsubsection{Merged Task-Type Processes} \index{solitary agent model!processing-only analysis!reward processes|(indexdef}% Define the random processes $(\Game^p_M)$, $(\mho^p_M)$, $(\daleth^p_M)$, and $(I^p_M)$ as merged versions of the families $((\hat{G}^i_M))_{i=1}^n$, $((\hat{C}^i_M))_{i=1}^n$, $((\hat{T}^i_M))_{i=1}^n$, and $((\hat{I}^i_M))_{i=1}^n$ respectively. Each of these processes is an \iid{}\ sequence of random variables, where $I^p_1$ and $\Upsilon^p_1$ are assumed to be independent. We use the notations \termdef{Cprocess.0510}{gp}{$g^p$}{Gross gain random variable for processing a task during one processing \aimention{Andrei A. Markov}Markov renewal cycle (points)}, \termdef{Cprocess.0520}{cp}{$c^p$}{Cost random variable for processing a task during one processing \aimention{Andrei A. Markov}Markov renewal cycle (points)}, and \termdef{Cprocess.0530}{taup}{$\tau^p$}{Time random variable for processing a task during one processing \aimention{Andrei A. Markov}Markov renewal cycle (seconds)} defined by % \begin{equation*} g^p \triangleq \Game^p_1 \quad \text{ and } \quad c^p \triangleq \mho^p_1 \quad \text{ and } \quad \tau^p \triangleq \daleth^p_1 \end{equation*} % These respectively represent the gain, cost, and time from processing during a single processing renewal cycle. % \index{solitary agent model!processing-only analysis!reward processes|)indexdef}% \index{solitary agent model!processing-only analysis!statistics|(indexdef}% We also define the symbols \termdef{Cprocess.0511}{avggp}{$\overline{g^p}$}{Expected gross gain for processing a task during one processing \aimention{Andrei A. Markov}Markov renewal cycle (points)}, \termdef{Cprocess.0521}{avgcp}{$\overline{c^p}$}{Expected cost for processing a task during one processing \aimention{Andrei A. Markov}Markov renewal cycle (points)}, and \termdef{Cprocess.0531}{avgtaup}{$\overline{\tau^p}$}{Expected time for processing a task during one processing \aimention{Andrei A. Markov}Markov renewal cycle (seconds)} with % \begin{equation*} \overline{g^p} \triangleq \E\left( g^p \right) = \E\left(\Game^p_1\right) \quad \text{ and } \quad \overline{c^p} \triangleq \E\left( c^p \right) = \E\left(\mho^p_1\right) \quad \text{ and } \quad \overline{\tau^p} \triangleq \E\left( \tau^p \right) = \E\left(\daleth^p_1\right) \end{equation*} % respectively. Therefore, % \begin{equation*} \overline{g^p} = \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} g_j \quad \text{ and } \quad \overline{c^p} = \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} c_j \tau_j \quad \text{ and } \quad \overline{\tau^p} = \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} \tau_j \end{equation*} % So, these expectations are weighted sums of parameters. In particular, if $n = 1$ (and $p_1 = 1$), % \begin{equation*} \overline{g^p} = g_1(\tau_1) \quad \text{ and } \quad \overline{c^p} = c_1 \tau_1 \quad \text{ and } \quad \overline{\tau^p} = \tau_1 \end{equation*} % This result is useful when visualizing optimization results. Additionally, % \begin{equation*} \E\left( C^s \Upsilon^p_1 | I^p_1 = i \right) = \E\left( C^s \Upsilon^p_1 \right) = \frac{c^s}{\lambda^p} \end{equation*} % We will use these results frequently in expressions of statistics of interest.% \index{solitary agent model!processing-only analysis!statistics|)indexdef}% %%fakeparagraph{Partial Derivatives:} %\paragraph{Partial Derivatives:} For all $i \in \{1,2,\dots,n\}$, %% %\begin{equation*} % \frac{ \partial \lambda^p }{ \partial p_i } = \lambda_i % \quad \text{ and } \quad % \frac{ \partial^2 \lambda^p }{ {\partial p_i}^2 } = % \frac{ \partial \lambda^p }{ \partial \tau_i } = % \frac{ \partial^2 \lambda^p }{ {\partial \tau_i}^2 } = % 0 %\end{equation*} %% %and %% %\begin{equation*} % \frac{ \partial \overline{g^p} }{ \partial p_i } % = % \frac{\lambda_i}{\lambda^p} % \left( g_i - \overline{g^p} \right) % \quad \text{ and } \quad % \frac{ \partial \overline{c^p} }{ \partial p_i } % = % \frac{\lambda_i}{\lambda^p} % \left( c_i \tau_i - \overline{c^p} \right) % \quad \text{ and } \quad % \frac{ \partial \overline{\tau^p} }{ \partial p_i } % = % \frac{\lambda_i}{\lambda^p} % \left( \tau_i - \overline{\tau^p} \right) %\end{equation*} %% %and %% %\begin{equation*} % \frac{ \partial \overline{g^p} }{ \partial \tau_i } % = % \frac{\lambda^p_i}{\lambda^p} g_i'(\tau_i) % \quad \text{ and } \quad % \frac{ \partial \overline{c^p} }{ \partial \tau_i } % = % \frac{\lambda^p_i}{\lambda^p} c_i % \quad \text{ and } \quad % \frac{ \partial \overline{\tau^p} }{ \partial \tau_i } % = % \frac{\lambda^p_i}{\lambda^p} %\end{equation*} %% %Thus, %% %\begin{equation} % \frac{ \partial }{ \partial p_i } % ( \lambda^p \overline{g^p} ) = \lambda_i g_i % \quad \text{ and } \quad % \frac{ \partial }{ \partial p_i } % ( \lambda^p \overline{c^p} ) = \lambda_i c_i \tau_i % \quad \text{ and } \quad % \frac{ \partial }{ \partial p_i } % ( \lambda^p \overline{\tau^p} ) = \lambda_i \tau_i % \label{eq:process_only_partial_p} %\end{equation} %% %and %% %\begin{equation} % \lambda^p \frac{ \partial \overline{g^p} }{ \partial \tau_i } % = \lambda_i p_i g_i'(\tau_i) % \quad \text{ and } \quad % \lambda^p \frac{ \partial \overline{c^p} }{ \partial \tau_i } % = \lambda_i p_i c_i % \quad \text{ and } \quad % \lambda^p \frac{ \partial \overline{\tau^p} }{\partial \tau_i} % = \lambda_i p_i % \label{eq:process_only_partial_tau} %\end{equation} %% %where $g_i'(\tau_i)$ reflects the first derivative of the $g_i(\tau_i)$ %parameter function. Notice the similarities between %\longrefs{eq:oft_partial_p} and \shortref{eq:process_only_partial_p} %and between \longrefs{eq:oft_partial_tau} and %\shortref{eq:process_only_partial_tau}. \subsection{Process-Only Markov Renewal Process} \aimention{Andrei A. Markov}% \index{solitary agent model!processing-only analysis!reward processes|(indexdef}% Define \iid{}\ random processes \termdef[$(G_{N^p})$]{Cprocess.11}{G1}{$G_1$}{Net gain from a single processing renewal cycle (points)}, \termdef[$(C_{N^p})$]{Cprocess.12}{C1}{$C_1$}{Cost from a single processing renewal cycle (points)}, and \termdef[$(T_{N^p})$]{Cprocess.13}{T1}{$T_1$}{Length of time of a single processing renewal cycle (seconds)} with % \begin{align*} G_{N^p} &\triangleq \Game^p_{N^p} - \mho^p_{N^p} - C^s \Upsilon^p_{N^p}\\ C_{N^p} &\triangleq \mho^p_{N^p} + C^s \Upsilon^p_{N^p}\\ T_{N^p} &\triangleq \daleth^p_{N^p} + \Upsilon^p_{N^p} \end{align*} % for all $N^p \in \N$ and $\zeta \in \set{U}$. Clearly, the \iid{}\ process $(G_{N^p}+C_{N^p})$ has $G_{N^p}+C_{N^p}=\Game^p_{N^p}$ for all $N^p \in \N$ and $\zeta \in \set{U}$. Also, $\Pr( T_1 = 0 ) = 0$ and % \begin{align} \E\left( G_1 \right) &= \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} \left( g_i - c_i \tau_i \right) - \frac{c^s}{\lambda^p} \label{eq:EG1} \\ \E\left( C_1 \right) &= \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} c_i \tau_i + \frac{c^s}{\lambda^p} \label{eq:EC1} \\ \E\left( T_1 \right) &= \frac{1}{\lambda^p} + \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} \tau_i \label{eq:ET1} \\ \E\left( G_1 + C_1 \right) &= \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} g_i \label{eq:EGC1} \end{align} % Because $0 < \E(T_1) < \infty$, define \termdef[$(N^p(t): t \in \R_{\geq0})$]{Cprocess.02}{Nt}{$N^p(t)$}{Number of tasks processed after $t$ seconds} with % \begin{equation*} N^p(t) \triangleq \sup \left\{ N^p \in \N : \sum\limits_{i=1}^{N^p} T_i \leq t \right\} \end{equation*} % for all $t \in \R_{\geq0}$ and $\zeta \in \set{U}$. That is, for all $\zeta \in \set{U}$, $N^p(t)$ is the \emph{total} number of tasks \emph{processed} from time $0$ to \emph{total} time $t$. % \index{solitary agent model!processing-only analysis!reward processes|)indexdef} \index{solitary agent model!processing-only analysis!renewal process|(indexdef}This is a \aimention{Andrei A. Markov}Markov renewal process depicted in \longref{fig:markov_process}, and one iteration around this process will be known as a \index{Markov renewal cycles!processing cycle|see{solitary agent model, processing-only analysis, processing cycle}}\index{processing cycle|see{solitary agent model, processing-only analysis, processing cycle}}\index{solitary agent model!processing-only analysis!processing cycle|indexdef}\emph{processing cycle}. % %\begin{figure}[!ht]\centering \begin{figure}\centering \begin{picture}(265,35)(0,0) \thinlines \put(0,20){\vector(1,0){50}} \put(52,20){\makebox(0,0)[l]{Find and Process}} \put(145,20){\line(1,0){120}} % \put(265,20){\line(0,-1){20}} \put(265,0){\line(-1,0){265}} \put(0,0){\line(0,1){20}} % \put(47.5,28){\circle*{5}} \end{picture} \caption[Process-Only Markov Renewal Process]{The process-only \aimention{Andrei A. Markov}Markov renewal process, where the solid dot is the renewal point that starts each \index{solitary agent model!processing-only analysis!processing cycle}cycle.} \label{fig:markov_process} \end{figure} % The holding time for this process \emph{always} includes \emph{both} search and processing time. Clearly, $(T_{N^p})$ is the interevent time process, $\aslim N^p(t) = \infty$, and $0 \leq \E( N^p(t) ) \leq \lambda^p t$ for all $t \in \R_{\geq0}$. \index{solitary agent model!processing-only analysis!renewal process|)indexdef}% \subsubsection{Cumulative Reward Processes and Their Statistics} \index{solitary agent model!processing-only analysis!reward processes|(indexdef}% \index{stochasticity!Markov renewal-reward process|(}% Define the cumulative processes $(G^{N^p})$, $(C^{N^p})$, and \termdef[$(G^{N^p})$]{Cprocess.31}{GN}{$G^{N^p}$}{Total net gain for $N$ processing \aimention{Andrei A. Markov}Markov renewal cycles (points)}, \termdef[$(C^{N^p})$]{Cprocess.32}{CN}{$C^{N^p}$}{Total cost for $N$ processing \aimention{Andrei A. Markov}Markov renewal cycles (points)}, and \termdef[$(T^{N^p})$]{Cprocess.33}{TN}{$T^{N^p}$}{Total length of time for $N^p$ processing \aimention{Andrei A. Markov}Markov renewal cycles (seconds)} with % \begin{equation*} G^{N^p} \triangleq \sum\limits_{i=1}^{N^p} G_i \quad \text{ and } \quad C^{N^p} \triangleq \sum\limits_{i=1}^{N^p} C_i \quad \text{ and } \quad T^{N^p} \triangleq \sum\limits_{i=1}^{N^p} T_i \end{equation*} % and the \aimention{Andrei A. Markov}Markov renewal-reward processes \termdef[$(G(t): t \in \R_{\geq0})$]{Cprocess.51}{Gt}{$G(t)$}{Total net gain after $t$ seconds (\ie, $G^{N^p(t)}$) (points)}, \termdef[$(C(t): t \in \R_{\geq0})$]{Cprocess.52}{Ct}{$C(t)$}{Total cost after $t$ seconds (\ie, $C^{N^p(t)}$) (points)}, and \termdef[$(T(t): t \in \R_{\geq0})$]{Cprocess.53}{Tt}{$T(t)$}{Total length of time after $t$ seconds for all completed processing \aimention{Andrei A. Markov}Markov renewal cycles (\ie, $T^{N^p(t)}$) (seconds)} with % \begin{equation*} G(t) \triangleq G^{N^p(t)} \quad \text{ and } \quad C(t) \triangleq C^{N^p(t)} \quad \text{ and } \quad T(t) \triangleq T^{N^p(t)} \end{equation*} % Clearly, processes $(G^{N^p}+C^{N^p})$ and $(G(t)+C(t):t \in \R_{\geq0})$ are well-defined. % \index{stochasticity!Markov renewal-reward process|)}% \index{solitary agent model!processing-only analysis!reward processes|)indexdef}% \index{solitary agent model!processing-only analysis!statistics|(indexdef}% Therefore, for all $N^p \in \N$ % \begin{equation*} \E\left( G^{N^p} \right) = N^p \E\left( G_1 \right) \enskip \text{ and } \enskip \E\left( C^{N^p} \right) = N^p \E\left( C_1 \right) \enskip \text{ and } \enskip \E\left( T^{N^p} \right) = N^p \E\left( T_1 \right) \end{equation*} % and so $\E( G^{N^p} + C^{N^p} ) = N^p \E( G_1 + C_1 )$. Also, for all $t \in \R_{\geq0}$, % \begin{align*} \E\left( G(t) \right) &= \E\left( N^p(t) \right) \E\left( G_1 \right)\\ \E\left( C(t) \right) &= \E\left( N^p(t) \right) \E\left( C_1 \right)\\ \E\left( T(t) \right) &= \E\left( N^p(t) \right) \E\left( T_1 \right) \end{align*} % and so $\E( G(t) + C(t) ) = \E( N^p(t) ) \E( G_1 + C_1 )$.% \index{solitary agent model!processing-only analysis!statistics|)indexdef}% \subsubsection{Limits of Cumulative Reward Processes} \index{solitary agent model!processing-only analysis!limits|(indexdef}% There exists\footnote{See \longref{app:markov_renewal_sto_limits}.} an $N^p \in \N$ such that $\E(1/N^p) < \infty$, so % \begin{equation} \aslim\limits_{t \to \infty} \frac{ G(t) }{t} = \lim\limits_{t \to \infty} \frac{ \E\left( G(t) \right) }{t} = \aslim\limits_{N^p \to \infty} \frac{ G^{N^p} }{ T^{N^p} } = \lim\limits_{N^p \to \infty} \E\left( \frac{ G^{N^p} }{ T^{N^p} } \right) = \frac{ \E\left(G_1\right) }{ \E\left(T_1\right) } \label{eq:payoff_long_rate} \end{equation} % and % \begin{equation} \aslim\limits_{t \to \infty} \frac{ N^p(t) }{t} = \lim\limits_{t \to \infty} \frac{ \E\left( N^p(t) \right) }{t} = \aslim\limits_{N^p \to \infty} \frac{ N^p }{ T^{N^p} } = \lim\limits_{N^p \to \infty} \E\left( \frac{ N^p }{ T^{N^p} } \right) = \frac{1}{ \E\left(T_1\right) } \label{eq:long_rate} \end{equation} % The ratio $\E(G_1)/\E(T_1)$ may be called the \index{long-term rate of net gain|see{long-term average rate of net gain}}\index{long-term average rate of net gain|(indexdef}\emph{long-term (average) rate of net gain} and has the expression % \begin{equation*} \frac{ \E\left(G_1\right) }{ \E\left(T_1\right) } = \frac { \overline{g^p} - \overline{c^p} - \frac{c^s}{\lambda^p} } { \frac{1}{\lambda^p} + \overline{\tau^p} } = \frac { \sum\limits_{i=1}^n \lambda^p_i ( g_i - c_i \tau_i ) - c^s } { 1 + \sum\limits_{i=1}^n \lambda^p_i \tau_i } = \frac {\lambda^p \left( \overline{g^p} - \overline{c^p} \right) - c^s} { 1 + \lambda^p \overline{\tau^p} } \end{equation*} % \index{long-term average rate of net gain|)indexdef}% So, % \begin{equation} \frac{ \E\left(G_1\right) }{ \E\left(T_1\right) } = \frac{ \E\left(G^N\right) }{ \E\left(T^N\right) } = \frac{ \E\left(G(t)\right) }{ \E\left(T(t)\right) } \label{eq:payoff_long_rate_equiv} \end{equation} % for all $N \in \N$ and $t \in \R_{>0}$. Additionally, $\E(G_1)/\E(T_1)=\E(\oft{G}_1)/\E(\oft{T}_1)$, which shows an important connection between this approach and the classical \index{optimal foraging theory}\ac{OFT} approach.% \index{solitary agent model!processing-only analysis!limits|)indexdef}% \subsubsection{Variance Under Pseudo-Deterministic Conditions}% \index{solitary agent model!processing-only analysis!statistics|(indexdef}% \index{solitary agent model!processing-only analysis!variance|(indexdef}% To define the variance of $(G^{N^p})$, $(C^{N^p})$, $(T^{N^p})$, and $(G^{N^p} + C^{N^p})$, we must again assume that \index{stochasticity!random variable!pseudo-deterministic}$\Pr( g^i_1 = g_i ) = \Pr( c^i_1 = c_i ) = \Pr( \tau^i_i = \tau_i ) = 1$ and that % \begin{enumerate}[(i)] \item For all $i \in \{1,2,\dots,n\}$, $X^p_1$ is uncorrelated with each of of $(g^i_1 - c^i_1 \tau^i_1)^2$, $(c^i_1 \tau^i_1)^2$, and $(\tau^i_1)^2$. \item $\Game^p_1$ is uncorrelated with $C^s \Upsilon^p_1$. \item $(C^s \Upsilon^p_1)^2$ is independent of $I^p_1$. \item $(C^s)^2$ is uncorrelated with $(\Upsilon^p_1)^2$. \item For all $i \in \{1,2,\dots,n\}$, $g^i_1$ is uncorrelated with $c^i_1 \tau^i_1$. \end{enumerate} % These assumptions yield the second moments % \begin{align} \E\left( \left(g^p\right)^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} \left( g_i \right)^2 \label{eq:cycle_proc_gross_gain_2moment} \\ % \E\left( \left(c^p\right)^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} \left( c_i \tau_i \right)^2 \label{eq:cycle_proc_cost_2moment} \\ % \E\left( \left(\tau^p\right)^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} \left( \tau_i \right)^2 \label{eq:cycle_proc_time_2moment} \\ % \E\left( \left(g^p - c^p\right)^2 \right) &= \sum\limits_{i=1}^n \frac{\lambda^p_i}{\lambda^p} \left( g_i - c_i \tau_i \right)^2 \label{eq:cycle_net_gain_2moment} \end{align} % which can be used to derive variances and other second moments. In particular, for all $N^p \in \N$, % \begin{align} \E\left( G_1^2 \right) &= \E\left( \left(g^p - c^p\right)^2 \right) - 2 \frac{c^s}{\lambda^p} \E\left( G_1 \right) \label{eq:net_gain_2moment} \\ \E\left( C_1^2 \right) &= \E\left( \left(c^p\right)^2 \right) - 2 \frac{c^s}{\lambda^p} \E\left( C_1 \right) \label{eq:cost_2moment} \\ \E\left( T_1^2 \right) &= \E\left( \left(\tau^p\right)^2 \right) - 2 \frac{1}{\lambda^p} \E\left( T_1 \right) \label{eq:time_2moment} \\ \E\left( \left( G_1 + C_1 \right)^2 \right) &= \E\left( \left(g^p\right)^2 \right) \label{eq:gross_gain_2moment} \end{align} % and % \begin{align} \var\left( G^{N^p} \right) &= N^p \left( \var\left( g^p - c^p \right) + \left( \frac{c^s}{\lambda^p} \right)^2 \right) \label{eq:net_gain_variance} \\ \var\left( C^{N^p} \right) &= N^p \left( \var\left( c^p \right) + \left( \frac{c^s}{\lambda^p} \right)^2 \right) \label{eq:cost_variance} \\ \var\left( T^{N^p} \right) &= N^p \left( \var\left( \tau^p \right) + \left( \frac{1}{\lambda^p} \right)^2 \right) \label{eq:time_variance} \\ \var\left( G^{N^p} + C^{N^p} \right) &= N^p \var\left( g^p \right) \label{eq:gross_gain_variance} \end{align} \index{solitary agent model!processing-only analysis!variance|)indexdef}% \index{solitary agent model!processing-only analysis!statistics|)indexdef}% \index{solitary agent model!processing-only analysis|)indexdef}% \section{Relationship Between Analysis Approaches} \label{sec:relationship_bw_approaches} \index{solitary agent model!comparison of analyses|(}% Recall that for all $i \in \{1,\dots,n\}$, $\lambda_i^p = p_i \lambda_i$. Keeping this in mind, it is clear that in general (\ie, for any $t \in \R_{\geq 0}$, $N, N^p \in \W$) % \begin{align} \E\left(G(t)\right) \neq \E\left(G^{N^p}\right) \neq \E\left(G_1\right) &\neq \E\left(\oft{G}_1\right) \neq \E\left(\oft{G}^N\right) \neq \E\left(\oft{G}(t)\right) \nonumber % \intertext{and} % \E\left(T(t)\right) \neq \E\left(T^{N^p}\right) \neq \E\left(T_1\right) &\neq \E\left(\oft{T}_1\right) \neq \E\left(\oft{T}^N\right) \neq \E\left(\oft{T}(t)\right) \nonumber \\ % \intertext{However,} % \frac{\E\left(G(t)\right)}{\E\left(T(t)\right)} = \frac{\E\left(G^{N^p}\right)}{\E\left(T^{N^p}\right)} = \frac{\E\left(G_1\right)}{\E\left(T_1\right)} &= \frac{\E\left(\oft{G}_1\right)}{\E\left(\oft{T}_1\right)} = \frac{\E\left(\oft{G}^N\right)}{\E\left(\oft{T}^N\right)} = \frac{\E\left(\oft{G}(t)\right)}{\E\left(\oft{T}(t)\right)} \label{eq:RoE_equivalence} \end{align} % for all $t \in \R_{>0}$ and $N,N^p \in \N$. Note the following. % \begin{enumerate}[(i)] \item $\E(\oft{T}_1) > 0$ and $\E(T_1) > 0$, and so all of the ratios in \longrefs{eq:RoE_equivalence} are well-defined. \item There are no restrictions on the sign of $\E(\oft{G}_1)$ or $\E(G_1)$. These can be negative, zero, or positive. \label{item:no_sign_gains} \item There are no restrictions on the sign of $\E(\oft{C}_1)$ or $\E(C_1)$. These can be negative, zero, or positive. \label{item:no_sign_costs} \end{enumerate} % Points (\shortref{item:no_sign_gains}) and (\shortref{item:no_sign_costs}) allow for flexible interpretations of \emph{gain} and \emph{cost}. With the appropriate assignment of signs, gains can be viewed as time-invariant costs, and costs can be viewed as time-varying gains. This shows the flexibility of this generalized model. The equalities in \longref{eq:RoE_equivalence} imply that the stochastic limits in \longref{eq:oft_long_rate} are equal to the stochastic limits in \longref{eq:long_rate}; regardless of approach, the long-term rate of net point gain is equivalent. For any number of processing cycles or \ac{OFT} cycles completed, the ratio of expected net gain to expected time will be equal. Processing is guaranteed in a processing cycle, so a single processing cycle has a higher expected net gain than a single \ac{OFT} cycle; however, the expected holding time of a processing cycle is longer because encounters with ignored tasks are included as part of the cycle's holding time. Thus, the ratio of expected net gain to expected time is the same for cycles of either type. \index{solitary agent model!comparison of analyses|)}% \section{Weaknesses of the Model} \label{sec:model_weaknesses} \index{model weaknesses|see{solitary agent model, weaknesses}}\index{solitary agent model!weaknesses|(indexdef}Several features are not included in the model. % \begin{description} \item\emph{Rates and Costs:} Recognition costs, variable search rates, and variable processing rates are not modeled. Also, although encounters are assumed to happen at random, they are assumed to be driven by a homogenous \aimention{Sim\'{e}on-Denis Poisson}Poisson process (\ie, the average rate of encounters is time-invariant). \item\emph{Perfect Detection:} When an agent encounters a task, its behavior depends upon the type of that task. The model assumes that the agent can detect task types with no error. This model has been built so that it may potentially be augmented with support for detection error. \item\emph{Linear Cost Model:} All costs are assumed to be linear in time in this model. Thus, given any interval of time, the cost of that interval of time is assumed to be the product of the length of that interval with some constant, which we call a \emph{cost rate}. In most cases, that rate need not be deterministic; however, it must be uncorrelated with the interval of time. \item\emph{Known Search Cost Rate:} Search costs are also assumed by linear with respect to time; however, they are also assumed to be deterministic. This assumption is necessary to use the results from renewal theory that are central to classical \ac{OFT} methods. Thus, in many cases where these results are not used, this deterministic assumption can be relaxed. \item\emph{Competition and Cooperation:} The direct effect of other agents (\eg, competition or cooperation) on the environment is not modeled here in any specific way. \Citet{Cody74} views this as a weakness of the early solitary foraging models and introduces an optimal diet model that incorporates multiple foragers competing for resources. However, the parameters of the \citeauthor{Cody74} model are too abstract to be specified with physical quantities, and each forager in the model has a coarse set of behavioral options. Additionally, many engineering applications fit the solitary model well (\eg, \index{examples!applications!autonomous vehicle}autonomous \index{examples!applications!surveillance}surveillance vehicles). \item\emph{State Dependency:} Our model is not state-dependent. That is, the reaction of an agent to an encounter does not change over its lifetime (\ie, it is a static model). \Citet{Schoener71} documents many cases where foragers adjust their behavior when satiated. \Citet{HouMc99} handle state-dependent behaviors mathematically and show that they will often be advantageous when compared to static behaviors. However, in engineering applications it may be desirable to have behaviors that do not change over time. For example, if the computational abilities of an agent are limited, complex state-dependent behavior may not be possible. There may also be biological examples where dynamic adaptations based on feedback are not feasible. Thus, optimization over a set of time-invariant behaviors may be desirable in a number of applications. \end{description} % Despite the limitations of the model, it is sufficiently generic to have utility in a wide range of applications. Adding any further complexity to the model may make solutions too complex to be practical for implementation. \index{solitary agent model!weaknesses|)indexdef}% \index{solitary agent model|)}