randomness in $L$). Using the rate expression from Theorem \[theorem:multirelay\_capacity\], we formulate the problem as a total cost MDP.

Such a deployment problem could be motivated by a situation where it is required to place a sensor (say, a video camera) to monitor an event or an object from a safe distance (e.g., the battlefront in urban combat, or a suspicious object that needs to be detonated, or a group of animals in a forest). In such a situation, the deployment agent, after placing the sensor, walk away from the scene of the event, along a forest trail, or a road, or a building corridor, placing relays as he walks, until a suitable safe sink location is found, in such a way that the number of relays is kept small while the end-to-end data rate is maximized.

Formulation as an MDP {#subsection:mdp_formulation}
---------------------

We now formulate the as-you-go deployment problem as an MDP.

### Deployment Policies

In the as-you-go placement problem, the person carries a number of nodes and places them as he walks, under the control of a placement policy. A deployment policy $\pi$ is a sequence of mappings $\{\mu_1,\mu_2, \mu_3, \cdots \}$ from the state space to the 