Serverless computing has become a major trend among cloud providers.
With serverless computing, developers fully delegate the task of managing the servers, dynamically allocating the required resources, as well as handling availability and fault-tolerance matters to the cloud provider.
In doing so, developers can solely focus on the application logic of their software, which is then deployed and completely managed in the cloud.

Despite its increasing popularity, not much is known regarding the actual system performance achievable on the currently available serverless platforms.
Specifically, it is cumbersome to benchmark such systems in a language- or runtime-independent manner.
Instead, one must resort to a full application deployment, to later take informed decisions on the most convenient solution along several dimensions, including performance and economic costs.

is a modular architecture and proof-of-concept implementation of a benchmark suite for serverless computing platforms.
It currently supports the current mainstream serverless cloud providers (i.e., AWS, Azure, Google, IBM), a large set of benchmark tests and a variety of implementation languages.
The suite fully automatizes the deployment, execution and clean-up of such tests, providing insights (including historical) on the performance observed by serverless applications.
also integrates a model to estimate budget costs for deployments across the supported providers.
is open-source and available at <https://github.com/bschitter/benchmark-suite-serverless-computing>.

[align=center] () at (0,0)
sharp corners]

CC-BY 4.0. This is the author's preprint version of the camera-ready article. A full version of this paper is published in the proceedings of 14th ACM International Conference on Distributed and Event-Based Systems (DEBS 2020).

§ INTRODUCTION

The serverless computing paradigm is an emerging approach for developing cloud-based applications <cit.>.
IBM <cit.> defines it as “an approach to computing that offloads responsibility for common infrastructure management tasks (scaling, scheduling, patching, provisioning, ) to cloud providers and tools, allowing engineers to focus their time and effort on the business logic specific to their applications or process”.
Serverless computing requires less expertise than other self-managed approaches.
Users do not manage directly the infrastructure and runtime of the system, but instead delegate its operations to the cloud provider.
Additionally, cloud providers can deploy finer-grain billing policies (, on a per service-call basis) for any of the offered services <cit.>, generally leading to reduced costs for developers.

Typical FaaS architecture. The main aspects to benchmark are: performance of a worker (, execution speed of a function) and quality of the auto-scaling mechanism (, allocation of new VMs, how to handle flash-crowds <cit.>).

One can distinguish between various serverless paradigms:
(1) FaaS (function as a service, and focus of our work) implemented for instance by AWS Lambda <cit.>,
(2) DBaaS (database as a service), as available through Microsoft Azure for PostgreSQL <cit.>; and
(3) STaaS (storage as a service), via Google Cloud <cit.>.
FaaS can be considered an hybrid between PaaS and the SaaS service model: data and infrastructure are fully managed by the provider, while the application is handled by the user.
<ref> illustrates a typical FaaS infrastructure.

In the typical FaaS approach, developers bypass the setup, maintenance and management of a compute node (, bare metal, virtual machines, or even containers).
Instead, users provide the application code for specific functions to be deployed to the cloud.
Specific events (, HTTP requests, storage or database conditions) trigger their execution, typically implementing data processing <cit.>.
The provider then handles the load, as well as availability and scaling requirements.
Despite the convenience of the approach, it is currently hard to decide on a specific FaaS provider based on criteria such as performance, workload adaptability or costs.

This paper introduces , a testing suite that tackles this problem.
In a nutshell, application developers can use the suite to automatically deploy several performance tests a set of FaaS providers.
The results can then be easily compared along several dimensions.
Based on this information, deployers can evaluate the “FaaS-domness” of the providers and decide which one is best adapted for their applications, in terms of performance, reliability or cost.

While few efforts exist to benchmark serverless computing (often FaaS oriented)  <cit.>, they are relatively limited in terms of supported providers, comparison metrics, diversity of benchmarks (, user-defined functions, elasticity), or operating modes (, stress-test vs. continuous monitoring).

Similarly, studies on benchmarking cloud platforms lack an in-depth evaluation of serverless computing platforms <cit.>.

In this paper, we introduce , a modular and extensible benchmark suite for evaluating serverless computing.
natively supports major FaaS providers (AWS, Azure, Google, IBM) but can be easily extended to benchmark additional platforms.
It includes a wide range of workloads, including user-defined functions, and implementation languages.
uses several metrics to compare FaaS platforms against multiple dimensions, in terms of latency, throughput and operating costs.
It provides a Web-based interface that allows users to perform benchmarks in a fully automatic way (including deployment, execution and clean-up of the tests), and keeps track of historical data.
In that way, can be used both for one-shot benchmarks and for continuous monitoring over time of the providers.
is the first system to support such in-depth, comprehensive and extensible benchmarking of serverless computing.

The remainder of this paper is organised as follows.
We first introduce background concepts (<ref>) and the supported frameworks (<ref>).
We then describe the architecture (<ref>) and its different benchmarks (<ref>).
We present and discuss evaluation results (<ref>), before concluding with a summary of lessons learned (<ref>) and open perspectives(<ref>).

§ BACKGROUND

This section provides technical details about the four major mainstream serverless providers, namely Amazon Web Services (<ref>), Microsoft Azure (<ref>), Google Cloud (<ref>) and IBM Cloud (<ref>).

We compare the performance of all of them in our evaluation (<ref>).

§.§ Amazon Web Services Lambda

AWS Lambda <cit.> was released in November in 2014 <cit.>.
AWS Lambda spans 18 geographical regions, plus China <cit.>.
At the time of writing, it supports six different runtime systems and seven different programming languages <cit.>.
Depending on the region where the function is deployed, Lambda supports up to 3,000 instances to serve the user functions <cit.>.
The memory allocated to a function instance can vary from 128 MB up to 3,008 MB in steps of 64 MB <cit.>.
The CPU power increases linearly with its memory allocation.
For instance, according to the documentation, at 1,792 MB the function will get 1 vCPU <cit.>.

As observed in <cit.>, Lambda executes functions using two different CPUs, namely Intel Xeon E5-2666 clocked at 2.90 GHz and Intel Xeon E5-2680, clocked at 2.80 GHz.

§.§ Microsoft Azure Functions

Microsoft Azure Functions <cit.> was released publicly in November 2016 <cit.>.
It supports five runtime systems and seven different programming languages <cit.>.
In contrast with the other three cloud providers, Azure offers three different hosting plans <cit.>:

Azure Functions offers billing plans that adapt to the load and popularity of the deployed function (“Consumption” plan), plans with finer-grain control over the computing instance size and pre-warming support (“Premium” plan), and a billing plan customized on a given application needs (“App Service” plan).
This work only considers the consumption plan (generation 2.0 <cit.>), as it is the only one to be fully managed by the cloud provider and the most similar in terms of features to the plans from alternative providers.

Azure Functions can use as many as 200 instances and up to 1.5 GB memory <cit.>.
The service can run either on Windows or Linux hosts, and is offered in 28 out of 46 publicly accessible regions <cit.>.
Note that the consumption plan is only available in 11 regions for both Linux and Windows, hence we restrict our deployment to those in our experiments.
Computing nodes can be characterized by their ACU, with 100 ACU roughly mapped to 1 vCPU.

According to our investigations, we believe Azure Functions to be executed by virtual machines of type Av2.[<https://docs.microsoft.com/de-ch/azure/virtual-machines/av2-series>]

These VMs use three different CPUs: Intel Xeon 8171M at 2.1 GHz, Intel Xeon E5-2673 v4 at 2.3 GHz and Intel Xeon E5-2673 v3 at 2.4 GHz <cit.>.

§.§ Google Cloud Functions

Google Functions <cit.> was released on July in 2018 <cit.> and is available through seven out of the twenty Google regions <cit.>.

It currently only supports three programming languages <cit.>, namely Node.js, Python and Go.
While there is not a maximum number of allocated instances per single function, it only allows up to 1,000 functions to be executed concurrently <cit.>.

<ref> summarizes the options for CPU and memory combinations supported by the platform <cit.>.
While the official documentation lacks details on the exact CPU models, a quick inspection of  unveils certain details, such as ,  and .
We only identified Intel-based processors during our experiments.

Memory/CPU configurations supported by Google Cloud Functions <cit.>.

Memory     128   MB      256   MB      512   MB      1,024   MB      2,048   MB

CPU        200   MHz     400   MHz     800   MHz       1.4   GHz       2.4   GHz

§.§ IBM Cloud Functions

IBM Cloud Functions <cit.> is built on top of Apache OpenWhisk, an open source serverless cloud platform using Docker containers <cit.>.
As such, in addition to Docker, it supports eight additional runtime systems <cit.>: Node.js, Python, Swift, PHP, Go, Java, Ruby and .NET Core.

The service is restricted to 1,000 concurrently active executions (including those enqueued for execution) per namespace <cit.>.

Memory allocation can be set from 128 MB to 2,048 MB in steps of 32 MB.
IBM Cloud Functions is available in five out of the six IBM regions <cit.>.[One region (Tokyo) lacks support for Cloud Foundry <cit.> and as such cannot be used to deploy functions via the CLI. We therefore did not include it in our evaluation.]

Our experiments revealed that some of the instances supporting the execution of the functions run on top of Intel Xeon E5-2683 v3 at 2.0 GHz.

§ RUNTIME SYSTEMS AND LANGUAGES

This section describes the runtime systems and programming languages supported by the serverless providers described in <ref>.

For the sake of comparisons and fairness of benchmarking, we are interested in those supported by multiple cloud providers.

<ref> highlights that Node.js is supported by all cloud providers.
We explain this by the fact the peculiar features of the language and the event-driven nature of the runtime make it particularly fit for serverless computing, as well as by its popularity among developers and its productivity advantages.

Python is similarly well supported, except by Azure on Windows.
Microsoft's  lacks support from Google.
In the remainder of this paper, we focus our comparison on the most supported runtime systems and languages, namely Node.js, Python, Go and .NET Core.
We briefly introduce them next.

Node.js. <cit.> is a JavaScript runtime built on Chrome's V8 JavaScript engine <cit.>.

The Node.js framework and the NPM have greatly contributed to making JavaScript a popular language to implement all kinds of applications.

<ref> shows the versions of Node.js supported by each cloud provider.

Because of its vast support from all providers, will deploy all Node.js applications using version 10.x.

Python is supported in multiple versions.
At the time of this writing, all cloud providers support version 3.7, hence we rely on this version for our benchmarking results.

Go <cit.> is supported by the FaaS providers for two recent releases of the language.
We use version 1.11 in our evaluation.

.NET Core is not uniformly supported by all the cloud providers.

Hence, uses 2.1 on AWS and 2.2 on Azure and IBM.
All  Core functions are implemented in the C dialect of the  framework.

§ ARCHITECTURE

This section describes the architecture of the prototype, depicted in <ref>, as well as providing some additional implementation details (<ref>).

The architecture includes the supported clouds and the corresponding serverless services (left), the involved Docker images (middle) and their interface with the system (right).
We detail each component next.

Main application.
The core component is implemented in JavaScript and leverages the Node.js framework.
It manages all user input and executes the actions or delegates them to other components.
This application is packaged and executed as Docker containers.

It manages the following main tasks:
(1) deployment to the clouds;
(2) execution of tests benchmarks; and
(3) computing price estimations.
Users access it through a Web-based GUI or via a REST API.
Once started, the set of configured tests are deployed for execution (some examples are given in <ref>).

Time series DB.
uses a time series database (TSDB) to store all the results from tests.
These results are subsequently used by graphical interfaces and pricing calculation.
Our prototype uses the InfluxDB <cit.> TSDB.

The architecture provides an API to easily integrate visualization tools.
Our prototype integrates with Grafana <cit.>, an open source tool to display, plot and monitor data stored in a database.
The results gathered by the tests and stored in InfluxDB are then displayed in Grafana.

With the exception of AWS, all cloud providers offer a Docker image for their CLI.
Resources can be deployed, deleted and managed completely by the CLI.

Runtime and languages (Node.js, Go, .NET).
In addition to the source code of the function(s) to execute, a pre-built and packaged zip file is commonly required to successfully complete the deployment.
The architecture allows developers to ship runtime images, necessary for instance to install packages and build/run the corresponding code.

Workload Injectors.
The architecture provides hook points for plugin workload injectors.
The evaluation results shown in <ref> uses  <cit.>, a stress tool for REST services, to issue requests toward services and gather throughput/latency results.

Web-based GUI.

Deployment steps for the different cloud providers supported by .

§.§ Deployment

Once the main application has started, the client can deploy the desired tests, for instance via the Web-based interface shown in <ref>.
Functions can be parametrized with memory allocated for each instance, timeouts, list of providers and runtime versions to use for the benchmarks, as well as geographical regions (as supported by the cloud provider) where to deploy the tests.

Once deployed, the interface continuously reports on the progress and potential issues (, timeouts, access problems, ).

The deployment process is parallelized, including the creation of the required cloud resources, the build and packaging of the functions, and their upload over the cloud.
The deployment flow is slightly different for each provider, with some providers requiring significantly more operations than others.
<ref> illustrates the various steps involved in the deployment for the providers supported by .

Upon cleanup, all deployed functions are permanently deleted, as well as all the configurations and resource groups created at deployment time.

§.§ Testing

When testing a serverless execution, will send every five seconds a request to the functions previously deployed, with the purpose to gather baseline results under low, constant load.
<ref> illustrates a screenshot of Grafana displaying the results of a latency test in Node.js.

Visualization of performance results in Grafana.

§.§ Benchmarking

For evaluating the performance of a deployed function, 's benchmarking component injects specific workloads toward the function exposed by a given serverless provider.
Our design is modular and currently supports  <cit.>, a constant throughput, correct latency HTTP benchmarking tool.
Additional tools are easy to integrate by providing a Docker container and a simple REST interface to exchange parameters and results.
The architecture allows users to directly visualize and analyze these results, using Grafana (<ref>) or other tools that can fetch the result data from the TSDB.

§.§ Billing Costs Calculator

provides a pricing calculator component, which can be used to evaluate beforehand the cost of executing a certain workload on the supported cloud providers.

Developers provide the planned workload (number of function invocations, execution time per call, size of the returned data and allocated memory, ).
The prototype produces an overview of the billing costs across the various serverless providers.
In future work, we envision this module to be able to forecast the billing costs even for full-fledged serverless applications, by applying machine-learning techniques to the system traces produced from sample executions serving real-world workloads.

§.§ Container Implementation

The implementation of extensively relies on Docker containers.
Specifically, the main container invokes other containers using a technique called Docker-in-Docker.[<https://www.docker.com/blog/docker-can-now-run-within-docker/>]
We do so by granting the main container access to  and mounting it as a volume.
During our evaluation, we did not observe any particular performance degradations using this approach.

The implementation of is freely available to the open-source community at <https://github.com/bschitter/benchmark-suite-serverless-computing>.
Its core components consist of about 2,000 lines of Node.js code.

Latency test scatter plot. Since  had issues with Node.js, we resort to  for that zone.

§ THE BENCHMARK SUITE

The benchmark suite consists of a collection of tests targeting different system aspects.
Each test is implemented in several programming languages in order to support the variety of the available runtime systems.
While there are some subtle differences across the code variants to adapt to the specificities of individual cloud providers, the code executed for each programming language is largely the same for all.
All functions are implemented using an HTTP trigger, as supported by all the serverless providers.
Currently, includes the followings benchmarks:

and  are two CPU-bound benchmarks to respectively factorize an integer and multiply large integer matrices.

is a network-bound test that immediately returns upon invocation, with a small JSON payload (HTTP body of 79 bytes and HTTP complete response including headers of $\sim$500 bytes). This test is used to verify the roundtrip times for geographically distributed deployments

is an IO-bound benchmark to evaluate the performance of a disk.
Perhaps surprisingly, each serverless cloud provides a temporary file-system that functions can use to read and write intermediate results.
Other functions executed by the same instance share this file-system to access its content.

is provided by to allows developers to test custom functions.
The suite provides templates for the currently supported cloud providers and the supported implementation languages.
In the long term, we expect the number of custom functions to greatly outnumber those provided by the suite itself.

§ EVALUATION

We present in this section the results of our evaluation using of the different FaaS providers supported by our current implementation.

We carried out these tests over a period of three weeks (Jan. 13–Feb. 4, 2020).
These experiments specifically aim at answering the following questions:
(1) what is the most effective programming language to use for serverless applications;
(2) what is the most convenient provider; and
(3) which provider yields the most predictable results.

Cold start latency.

§.§ Call Latency

We begin by measuring the latency (round-trip) for all cloud providers and corresponding regions, using the  benchmark.

Unless specified otherwise, we deploy Node.js using 128 MB.
We note that AWS functions run under a custom kernel 4.14.138-99.102.amzn2.x86_64;[<https://docs.aws.amazon.com/lambda/latest/dg/lambda-runtimes.html>]
whole host configurations are not disclosed for Azure, Google or IBM deployments.

A request is sent every 5 seconds to each cloud and region, up to 100 samples per function.
<ref> reports our results across 39 different configurations.

The average latency over all clouds and regions is 538 ms.
We achieve the fasted result on AWS Lambda () at 80 ms, and the slowest toward Google () at 1,770 ms.
Overall, the best performing cloud provider is Amazon, with slightly lower latency for the same geographical locations of other providers.
Note that this benchmark was performed from Bern, Switzerland, hence different results might be achieved from different locations.

Workflow for cold and warm start on Azure <cit.>.

Execution time of  in Python.

Execution time of  in Node.js.

§.§ Cold Start

A cold start happens when a function takes longer than usual to execute.
Most of the time, this occurs when the invocation is scheduled right after the completion of its deployment, or when the function has not been used in a while, , after 10 minutes without invocations.

Specifically, there are several steps to perform before a function can execute: allocate a server, set up a worker with the associated code, packages and extensions, load the function in memory, and finally run it.
These steps contribute clearly to the cold start effect that we observe in our results.
When the function is warm, it is ready in memory and can immediately serve requests.
A function can also be de-allocated (, garbage-collected) when a new instance needs to be provisioned for scaling purposes.

Execution time of  in Go.

Execution time of the  in .NET.

When this happens and an invocation is scheduled for the just garbage-collected function, the cold start effect is clearly measurable with degrading effects on the measured latency.

<ref> shows the execution workflow for a cold start on Azure, as opposed to the warm case.
Similar workflows (and effects on latency) exist on the other cloud providers.[Refer for instance to <https://cloud.google.com/functions/docs/bestpractices/tips> for information and best practices from Google.]

Our results are averaged over ten executions for each configuration runtime/cloud.
Functions are executed using 512 MB of memory and without external packages, to reduce the baseline footprint and the corresponding loading time to the bare minimum.

We executed these tests on the following regions:  for AWS,  for Azure,   for Google and  for IBM.
Note however that the chosen region has no impact on the cold start latency.
We compute the cold start latency as the total request time minus the normal average latency.
On AWS and IBM, cold starts can be deteced with the help of instance IDs.
On Azure and Google, online metrics of running instances were taken into account to verify cold starts.
The challenge of cold start detection lead to a manual test execution and data manipulation.

<ref> summarizes our results using a box-and-whiskers plot.
It stands out that AWS is overall the fastest, with an average cold start latency of only 335 ms for Node.js, Python and Go.
Results with .NET are worse, with latencies up to 1,739 ms, likely due to the nature of the runtime and the compilation of C#.
On Azure, cold start latency is strictly more than 2 seconds and up to 5 seconds, with the exception of the combination .NET on Windows, which averages at 1,917 ms.
IBM compares similarly to AWS.
Finally, Google Cloud consistently yields higher cold start latencies, in the 2-3 seconds range.
IBM exhibits a performs similarly to AWS across the spectrum of supported languages, although the cold start latency is around 600 ms higher for Node.js, Python and Go but similar for .NET.

On AWS and IBM, it took usually around 10 minutes of no activity for the computing instance to be recycled by the provider and re-inserted into the pool of available ones, and up to 20 minutes on Azure.
On Google, this time varied from 10 minutes up to 10 hours.

§.§ CPU-bound Benchmarks

This benchmark evaluates how CPU-bound workloads behave across the different cloud providers.

A function () is invoked every five seconds, using as parameter a large integer triggering a sufficiently challenging computation.
We collect 100 results for every configuration (runtime, memory, cloud provider).

We report these results for all cloud configurations and languages: Python (<ref>), Node.js (<ref>), Go (<ref>) and .NET (<ref>).

We note a few interesting facts.
On AWS Lambda, the standard deviation is low, with a minimum value of 50 ms using .NET and  2,048 MB of memory, with very consistent execution times across all the different configurations.
As expected, every doubling of the allocated memory results in halving the execution time, , performance scales linearly with allocated memory <cit.>.

Azure's memory configuration of 1,536 MB suggests its performance to be in the 1,024-2,048 MB range.
Surprisingly, it is slower than 1,024 MB instances of the other clouds.
Google Cloud Platform performs similarly to AWS, although more scattered for 128 MB of memory.
Google achieves better results than AWS for several memory configurations (128, 256, 512 and 1,024 MB).
Note however that the performance scaling behaves differently on the Google platform <cit.>.

The results we gathered on the IBM platform suggests that memory allocation does not correlate with CPU allocation in any way, with five different configurations performing very closely.
This is remarkable since the pricing model of IBM only accounts for the GB-seconds used.

Throughput/latency benchmark using  <cit.> and 's   stress function.

Latency: goal/target, results in the long-tail (below 90% of the target requests/sec).

Cloud     Runtime     Req/s (goal)     Req/s (actual)     Req/s (%)

Azure     Node.js     200     179     89.50%

Azure     Node.js     400     227     56.75%

Azure     Node.js     800     278     34.75%

Azure     Node.js     1000     327     32.70%

Azure     Python     10     6     60.00%

Azure     Python     25     12     48.00%

Azure     Python     50     18     36.00%

Azure     Python     100     25     25.00%

Azure     Python     200     30     15.00%

Azure     Python     400     15     3.75%

Azure     Python     800     14     1.75%

Azure     Python     1000     15     1.50%

Azure     .NET     400     324      81.00%

Azure     .NET     800     407     50.88%

Azure     .NET     1000     512     51.20%

Google     Python     25     12     48.00%

Google     Python     200     168     84.00%

Google     Python     400     297     74.25%

Google     Python     800     575     71.88%

IBM     Go     25      21     84.00%

§.§ Throughput/Latency

To understand the saturation point of the deployed services, we rely on  <cit.>, a constant throughput/exact latency HTTP-based benchmarking tool.
We configure this benchmark to issue function call invocations at increasingly high rates, from 10 up to 1,000 requests per second.
For each of the configurations,  reports the average latency to handle the requests (, the functions).
Between each configuration, the benchmark waits for sufficient time to process any request still possibly enqueued.
<ref> shows our results for the  function and the 4 different programming languages under test.

We observe that AWS achieves stable response latencies for all the tested workloads.

Azure, on the other hand, shows more surprising results.
Whereas it can tolerate high loads on Windows OS, it performs very inconsistently on Linux.
The response latency grows almost linearly with the total requests per second injected and quickly saturates.
That is a strong indication that none (or too few) new instances were allocated to handle the load.
We investigated this behaviour further through the Azure portal Live Metrics Stream (not shown).
When reaching 1,000 requests per second, only a total of 12 instances were deployed to serve .NET functions.
Additionally, only 500 requests per second were actually served, leaving a large percentage of requests in the waiting queue.

For Node.js and .NET, response latencies spike up to 24 s and 18 s, respectively.
Using Python, Azure managed to handle up to 200 requests per second, beyond which none of the requests could be served correctly.
Google can manage the load generally well, although latency increases slightly for Node.js and Go.
However, Python functions deployed Google suffer from poor performance, in particular at higher request rates.
Results suggest poor capacity in adapting quickly to flash-crowd requests, with the average request duration growing from 1,356 to 18,448 ms when increasing the rate from 10 to 25 requests per second.

We investigate further (<ref>) by analyzing the scaling behaviour for instances running Google Functions.
The plot shows the number of instances allocated during the load test on Google, suggesting indeed that the auto-scalability features provided by the infrastructure might lead to poor results as requests start saturating the deployed instances.

Google Go: number of active compute instances during the wrk2 load test.

On IBM Cloud Functions, Node.js performs particularly poorly when compared to the other providers, while Python functions perform on par with AWS.
Go functions achieve far worse than for other providers, contrasting with the cold start results that suggested similar behaviour.
Further investigation is needed as part of future work to understand the reasons of this behaviour.

<ref> reports for which cases the target throughput set by  could not be reached within a 10% margin, , cases achieving at most 90% of the target throughput (right-most column).

Pricing calculation: cost of the CPU-bound benchmarks computed by according to the pricing models of each cloud. Execution times are rounded up to the next 100 ms for AWS, Google and IBM <cit.>.

Memory     Exec. time      Invocation     GB/sec     GHz/sec     BW     Total

128 MB     8000 ms      2.00$       166.67$       —     3.43$     172.10$

256 MB     4000 ms      2.00$       166.67$       —     3.43$     172.10$

512 MB     2000 ms      2.00$       166.67$       —     3.43$     172.10$

1 GB       1000 ms      2.00$       166.67$       —     3.43$     172.10$

2 GB      600 ms      2.00$       200.00$       —     3.43$     205.43$

128 MB     1267 ms      2.00$        25.34$          —            3.32$      30.66$

128 MB     7700 ms      4.00$        24.06$          154.00$     4.58$     186.64$

256 MB     3200 ms      4.00$        20.00$          128.00$     4.58$     156.58$

512 MB     1600 ms      4.00$        20.00$          128.00$     4.58$     156.58$

1 GB        900 ms      4.00$        22.50$          126.00$     4.58$     157.08$

2 GB      800 ms      4.00$        40.00$          192.00$     4.58$     240.58$

128 MB     700 ms      —             14.88$          —            —           14.88$

256 MB     600 ms      —             25.50$          —            —           25.50$

512 MB     600 ms      —             51.00$          —            —           51.00$

1 GB       600 ms      —            102.00$          —            —           102.00$

2 GB       700 ms      —            238.00$          —            —           238.00$

§.§ Pricing

We conclude our quantitative evaluation by showcasing one possible usage of 's billing calculator (<ref>).
To that end, we use it to evaluate the cost of the CPU-bound benchmarks if executed across all the serverless providers.

We assume a Python runtime and 10 M function calls/months.

The allowed memory is set to a 100 MB function and a return payload of 4 KB per call.

We note that Azure supposedly charges the GB-seconds that the function actually used, rounded up to the next 128 MB step <cit.>.
It seems therefore that the pricing model of Azure is similar to the one of IBM, delivering the same performance independent of the memory size.

<ref> shows the costs computed by .

We observe that AWS is particularly accurate: for every doubling of memory, execution time halves, keeping the costs constant.
Despite not being the cheapest option, it remains the most predictable one.

Azure is the cheapest cloud provider according to our computations.
Since this example function application only uses 100 MB, Azure also only charges for 128 MB: memory is dynamically allocated and only billed according to the next 128 MB step.

The costs of deploying Google Functions follows closely those of AWS, especially for mid-range configurations.
For the least- and most-expensive configurations, AWS reveals to not be the best trade-off in terms of cost/performance.
Finally, IBM's billing method offers predictable costs, being roughly linearly dependant of the chosen memory configurations.

§.§ Usability Considerations

We finally report on some usability considerations regarding the cloud providers and their serverless offerings.

AWS Lambda.
Overall, this reveals to be the best-performing cloud provider.
According to our continuous monitoring over several months, it provides consistent performance and reliability.
Management via the CLI or Web-based portal is straightforward and efficient, even though setting up HTTP triggers remain convoluted.

(i) lack of official Docker image for the AWS CLI;
(ii) deleting a function requires usage of , which however only works on a per-region basis;
(iii) security counter-measures imposed by the AWS (, changing public APIs more frequently than 30 s) can reduce the productivity of the developers as well as the ability of quickly prototyping and testing functions.

Azure Functions.
Performance and usability are worse than AWS.
The cold start latency of 2 to 4 s makes it unfit for short-lived sessions.
The Web-based portal provides useful insights on the real-time performance, as well as system insights from telemetry-based monitoring on the supporting computing instances.

(i) there is a discrepancy between the actions available via the official CLI and the Web-based portal;
(ii) additional tools are required also for local debugging (, the Azure Functions core tools,[<https://github.com/Azure/azure-functions-core-tools>]), which seems counter-intuitive, and they are not shipped with any official Docker image;
(iii) the overall architecture, as well as the different generations of APIs, contribute in making the learning curve for Azure rather steep.

Google Cloud Functions.
This offering leverages a simple and clearly structured Web portal, as well as a consistent CLI tool.
Support for single-command operations is particularly helpful and practical.

While cold start latency is higher than AWS or IBM, it remains within usable limits.
Regarding billing costs, Google is the least convenient operator.

(i) the monitoring measurements available to the developers lag several minutes behind the real execution, preventing prompt interventions.
(ii) it supports a limited number of runtime systems, at the risk of being a less attractive deployment choice;
(iii) deployers are left with very few configuration options, preventing (by design) fine-tuning operations by the clients.

IBM Cloud Functions.
The current public release of IBM lacks straightforward and well-structured documentation.
The cold-start performance suggests this provider to be a good candidate for quick tests, where an application can start invoking functions with short waiting times.

(i) the official IBM CLI can only be used if there is a corresponding cloud foundry support for the intended region (currently the case for all public regions except for Tokyo);
(ii) the support for the Go runtime is rather poor, resulting in the worst performance for this configuration;
(iii) some (important) features are left undocumented, such as the limit of 3,000 request per minute authorized for normal accounts.

§ LESSONS LEARNED

This study has shown that serverless computing in the form of FaaS can deliver good performance at a reasonable price.
It is fairly easy to set up, deploy and execute code in the cloud for the end user, as compared to VMs or even physical servers.
With serverless computing, companies can focus on building their business logic instead of maintaining operating systems and servers on premises, which requires expertise and is not always affordable for small companies.
One of the most important features of FaaS is is auto-scaling capability, which take away from the deployer the burden of dimensioning the system and allocating resources.

Through the implementation and evaluation of , we notably encountered the following limitations of the FaaS paradigm.

First, one is heavily limited by the offering of specific cloud providers, including available runtime systems and programming languages, supported triggers, third party  services integration, quotas or maximum memory.
Users cannot easily overcome such limitations as the full application stack is managed by the provider.

Second, providers can force an application to migrate from a specific runtime version to an arbitrarily different one (, when upgrading their system from Node.js v6 to v8).
Despite backward compatibility, functions might break, forcing developers to keep up with the pace imposed by the cloud provider.

Third, developers face the risk of vendor lock-in by depending on proprietary features.
This might become a serious issue when considering application upgrades and potential provider migrations.

Finally, the lack of deployment standards makes the FaaS paradigm still a largely experimental playground.
Providers offer custom APIs (, request/response objects), which inevitably vary across cloud offerings.
A common framework supported by a standard would certainly improve adoption and benefit the whole ecosystem.

§ CONCLUSION AND FUTURE WORK

Motivated by the lack of common FaaS framework or standard platform to evaluate serverless platforms, this paper presented , a user-space application that facilitates performance testing across a variety of serverless platform.
is an open-source benchmark suite that is easy to deploy and provides meaningful insights across a variety of metrics and serverless providers.

We envision to extend along the following directions.
First, we will expand the set of supported languages and runtime systems, also by integrating contributions from the open-source community.
Second, we plan to maintain a continuous, online deployment of the , publicly accessible, in order to build a larger dataset of historical measurements that will be released to the research community.
We finally intend to include native support for Docker images to ship functions, in order to facilitate integration with services such as Google Cloud Run <cit.>.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

titleGrafana - he open observability platform.

Last accessed: 26.03.2020.

titleInfluxDB - the open source time series database.

Last accessed: 26.03.2020.

titleApache OpenWhisk.

Last accessed: 05.11.2019.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.
titleAWS Lambda.

Last accessed: 22.10.2019.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.
titleAWS Lambda Function Configuration.

Last accessed: 22.10.2019.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.
titleAWS Lambda Function Scaling.

Last accessed: 22.10.2019.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.
titleAWS Lambda Pricing.

Last accessed: 22.01.2020.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.
titleAWS Lambda Releases.

Last accessed: 22.10.2019.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.
titleAWS Lambda Runtimes.

Last accessed: 22.10.2019.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.
titleAWS Region Table.

Last accessed: 10.12.2019.

[AWS, Amazon Web ServicesAWS, Amazon Web
authorpersonAWS, Amazon Web Services.

Last accessed: 18.12.2019.

[Baldini, Castro, Chang, Cheng, Fink, Ishakian,
Mitchell, Muthusamy, Rabbah, Slominski, and SuterBaldini
et al2017]
authorpersonIoana Baldini, personPaul
Castro, personKerry Chang, personPerry Cheng,
personStephen Fink, personVatche Ishakian,
personNick Mitchell, personVinod Muthusamy,
personRodric Rabbah, personAleksander Slominski,
and personPhilippe Suter. year2017.
Serverless Computing: Current Trends and Open
Problems. In booktitleResearch Advances in Cloud
Computing, editorpersonSanjay Chaudhary,
personGaurav Somani, and personRajkumar Buyya
(Eds.). publisherSpringer Singapore,
addressSingapore, pages1–20.

[Castro, Ishakian, Muthusamy, and
SlominskiCastro et al2019]
authorpersonPaul Castro, personVatche
Ishakian, personVinod Muthusamy, and
personAleksander Slominski. year2019.
The Rise of Serverless Computing.
journalCommun. ACM volume62,
number12 (dateNov. year2019),

[Eyk, Scheuner, Eismann, Abad, and IosupEyk
et al2020]
authorpersonErwin Van Eyk, personJoel
Scheuner, personSimon Eismann, personCristina L.
Abad, and personAlexandru Iosup.
Beyond Microbenchmarks: The SPEC-RG Vision for a
Comprehensive Serverless Benchmark. In booktitleCompanion
of the 2020 ACM/SPEC International Conference on Performance Engineering,
ICPE 2020, Edmonton, AB, Canada, April 20-24, 2020,
editorpersonJosé Nelson Amaral,
personAnne Koziolek, personCatia Trubiani, and
personAlexandru Iosup (Eds.). publisherACM,

[Figiela, Gajek, Zima, Obrok, and
MalawskiFigiela et al2018]
authorpersonKamil Figiela, personAdam
Gajek, personAdam Zima, personBeata Obrok, and
personMaciej Malawski. year2018.
Performance evaluation of heterogeneous cloud
journalConcurrency and Computation: Practice and
Experience volume30, number23
(year2018), pagese4792.

e4792 cpe.4792.

[Gan, Zhang, Cheng, Shetty, Rathi, Katarki,
Bruno, Hu, Ritchken, Jackson, Hu, Pancholi, He, Clancy, Colen, Wen, Leung,
Wang, Zaruvinsky, Espinosa, Lin, Liu, Padilla, and DelimitrouGan
et al2019a]
authorpersonYu Gan, personYanqi Zhang,
personDailun Cheng, personAnkitha Shetty,
personPriyal Rathi, personNayan Katarki,
personAriana Bruno, personJustin Hu,
personBrian Ritchken, personBrendon Jackson,
personKelvin Hu, personMeghna Pancholi,
personYuan He, personBrett Clancy,
personChris Colen, personFukang Wen,
personCatherine Leung, personSiyuan Wang,
personLeon Zaruvinsky, personMateo Espinosa,
personRick Lin, personZhongling Liu,
personJake Padilla, and personChristina
Delimitrou. year2019a.
An Open-Source Benchmark Suite for Microservices
and Their Hardware-Software Implications for Cloud & Edge Systems. In
booktitleProceedings of the Twenty-Fourth International
Conference on Architectural Support for Programming Languages and Operating
Systems, ASPLOS 2019, Providence, RI, USA, April 13-17, 2019,
editorpersonIris Bahar, personMaurice
Herlihy, personEmmett Witchel, and personAlvin R.
Lebeck (Eds.). publisherACM, pages3–18.

[Gan, Zhang, Cheng, Shetty, Rathi, Katarki,
Bruno, Hu, Ritchken, Jackson, Hu, Pancholi, He, Clancy, Colen, Wen, Leung,
Wang, Zaruvinsky, Espinosa, Lin, Liu, Padilla, and DelimitrouGan
et al2019b]
authorpersonYu Gan, personYanqi Zhang,
personDailun Cheng, personAnkitha Shetty,
personPriyal Rathi, personNayan Katarki,
personAriana Bruno, personJustin Hu,
personBrian Ritchken, personBrendon Jackson,
personKelvin Hu, personMeghna Pancholi,
personYuan He, personBrett Clancy,
personChris Colen, personFukang Wen,
personCatherine Leung, personSiyuan Wang,
personLeon Zaruvinsky, personMateo Espinosa,
personRick Lin, personZhongling Liu,
personJake Padilla, and personChristina
Delimitrou. year2019b.
An Open-Source Benchmark Suite for Microservices
and Their Hardware-Software Implications for Cloud & Edge Systems. In
booktitleProceedings of the Twenty-Fourth International
Conference on Architectural Support for Programming Languages and Operating
Systems (seriesASPLOS '19). publisherACM,
addressNew York, NY, USA, pages3–18.

authorpersonGo. year2019.
titleThe Go Project.

Last accessed: 10.12.2019.

titleCloud Functions.

Last accessed: 29.10.2019.

titleCloud Functions - Pricing.

Last accessed: 30.10.2019.

titleCloud Functions - Quotas.

Last accessed: 30.10.2019.

titleCloud Functions - Release Notes.

Last accessed: 30.10.2019.

titleCloud Functions - Writing Cloud Functions.

Last accessed: 30.10.2019.

titleCloud Functions Locations.

Last accessed: 10.12.2019.

titleCloud Run (fully managed) release notes.

Last accessed: 07.02.2020.

authorpersonGoogle. year2019.
titleServerless computing.

Last accessed: 18.12.2019.

[Hellerstein, Faleiro, Gonzalez,
Schleier-Smith, Sreekanti, Tumanov, and WuHellerstein
et al2019]
authorpersonJoseph M. Hellerstein,
personJose M. Faleiro, personJoseph Gonzalez,
personJohann Schleier-Smith, personVikram
Sreekanti, personAlexey Tumanov, and
personChenggang Wu. year2019.
Serverless Computing: One Step Forward, Two Steps
Back. In booktitleCIDR 2019, 9th Biennial Conference on
Innovative Data Systems Research, Asilomar, CA, USA, January 13-16, 2019,
Online Proceedings. publisherwww.cidrdb.org.

authorpersonIBM. year[n.d.]a.
titleCloud Foundry.

Last accessed: 07.02.2020.

authorpersonIBM. year[n.d.]b.
titleIBM Cloud Functions.

Last accessed: 30.10.2019.

authorpersonIBM. year[n.d.]c.
titleIBM Cloud Functions - Pricing.

Last accessed: 22.01.2020.

titleIBM Cloud Functions - Runtimes.

Last accessed: 05.11.2019.

titleIBM Cloud Functions - Regions.

Last accessed: 10.12.2019.

titleIBM Cloud Functions - System details and limits.

Last accessed: 05.11.2019.

authorpersonIBM. year2019d.
titleServerless computing.

Last accessed: 18.12.2019.

[Jonas, Pu, Venkataraman, Stoica, and
RechtJonas et al2017]
authorpersonEric Jonas, personQifan Pu,
personShivaram Venkataraman, personIon Stoica, and
personBenjamin Recht. year2017.
Occupy the cloud: distributed computing for the
99%. In booktitleProceedings of the 2017 Symposium on
Cloud Computing, SoCC 2017, Santa Clara, CA, USA, September 24-27, 2017.
publisherACM, pages445–451.

[Jung, Krishnamurthy, and RabinovichJung
et al2002]
authorpersonJaeyeon Jung, personBalachander
Krishnamurthy, and personMichael Rabinovich.
Flash crowds and denial of service attacks:
Characterization and implications for CDNs and web sites. In
booktitleProceedings of the 11th international conference on
World Wide Web. pages293–304.

authorpersonYochay Kiriaty.
titleAnnouncing general availability of Azure Functions.

Last accessed: 29.10.2019.

[Kuhlenkamp, Werner, Borges, Ernst, and
WenzelKuhlenkamp et al2020]
authorpersonJörn Kuhlenkamp,
personSebastian Werner, personMaria C. Borges,
personDominik Ernst, and personDaniel Wenzel.
Benchmarking elasticity of FaaS platforms as a
foundation for objective-driven design of serverless applications. In
booktitleSAC '20: The 35th ACM/SIGAPP Symposium on
Applied Computing, online event, [Brno, Czech Republic], March 30 - April 3,
2020, editorpersonChih-Cheng Hung,
personTomás Cerný, personDongwan Shin,
and personAlessio Bechini (Eds.). publisherACM,

[Kuntsevich, Nasirifard, and
JacobsenKuntsevich et al2018]
authorpersonAleksandr Kuntsevich,
personPezhman Nasirifard, and personHans-Arno
Jacobsen. year2018.
A Distributed Analysis and Benchmarking Framework
for Apache OpenWhisk Serverless Platform. In
booktitleProceedings of the 19th International Middleware
Conference (Posters) (seriesMiddleware '18).
publisherACM, addressNew York, NY, USA,

[Lee, Satyam, and FoxLee
et al2018]
authorpersonHyungro Lee, personKumar
Satyam, and personGeoffrey Fox.
Evaluation of Production Serverless Computing

[Malawski, Figiela, Gajek, and ZimaMalawski
et al2018]
authorpersonMaciej Malawski, personKamil
Figiela, personAdam Gajek, and personAdam Zima.
Benchmarking Heterogeneous Cloud Functions. In
booktitleEuro-Par 2017: Parallel Processing Workshops,
editorpersonDora B. Heras, personLuc
Bougé, personGabriele Mencagli, personEmmanuel
Jeannot, personRizos Sakellariou, personRosa M.
Badia, personJorge G. Barbosa, personLaura Ricci,
personStephen L. Scott, personStefan Lankes, and
personJosef Weidendorfer (Eds.). publisherSpringer
International Publishing, addressCham,

titleAzure Database for PostgreSQL.

Last accessed: 11.03.2020.

titleAzure Functions.

Last accessed: 07.02.2020.

titleAzure Functions pricing.

Last accessed: 22.01.2020.

titleAzure Functions runtime versions overview.

Last accessed: 15.01.2020.

titleAzure Functions scale and hosting.

Last accessed: 29.10.2019.

titleGeneral purpose virtual machine sizes - Av2-series.

Last accessed: 29.10.2019.

titleProducts available by region.

<https://azure.microsoft.com/en-us/global-infrastructure/services/?products=functions   regions=all>

Last accessed: 10.12.2019.

titleSupported languages in Azure Functions.

Last accessed: 29.10.2019.

titleServerless computing.

Last accessed: 18.12.2019.

[Müller, Marroquin, and
AlonsoMüller et al2019]
authorpersonIngo Müller, personRenato
Marroquin, and personGustavo Alonso.
Lambada: Interactive Data Analytics on Cold Data
using Serverless Cloud Infrastructure.
journalCoRR  volumeabs/1912.00937

[Node.js FoundationNode.js
authorpersonNode.js Foundation.

Last accessed: 07.11.2019.

[Somu, Daw, Bellur, and KulkarniSomu
et al2020]
authorpersonNikhila Somu, personNilanjan
Daw, personUmesh Bellur, and personPurushottam
Kulkarni. year2020.
PanOpticon: A Comprehensive Benchmarking Tool for
Serverless Applications. In booktitle2020 International
Conference on COMmunication Systems & NETworkS, COMSNETS 2020,
Bengaluru, India, January 7-11, 2020. publisherIEEE,

authorpersonGil Tene. year2019.
titlewrk2 - a HTTP benchmarking tool based mostly on wrk.

Last accessed: 04.02.2020.

[Tilkov and VinoskiTilkov and
authorpersonStefan Tilkov and personSteve
Vinoski. year2010.
Node.js: Using JavaScript to build
high-performance network programs.
journalIEEE Internet Computing
volume14, number6 (year2010),

authorpersonColby Tresness.
titleUnderstanding serverless cold start.

Last accessed: 22.01.2020.

[van Eyk, Iosup, Seif, and Thömmesvan Eyk
et al2017]
authorpersonErwin van Eyk, personAlexandru
Iosup, personSimon Seif, and personMarkus
Thömmes. year2017.
The SPEC Cloud Group's Research Vision on FaaS and
Serverless Architectures. In booktitleProceedings of the
2Nd International Workshop on Serverless Computing
(seriesWoSC '17). publisherACM,
addressNew York, NY, USA, pages1–4.

[Wang, Li, Zhang, Ristenpart, and SwiftWang
et al2018]
authorpersonLiang Wang, personMengyuan Li,
personYinqian Zhang, personThomas Ristenpart, and
personMichael Swift. year2018.
Peeking Behind the Curtains of Serverless
Platforms. In booktitle2018 USENIX Annual Technical
Conference (USENIX ATC 18). publisherUSENIX Association,
addressBoston, MA, pages133–146.


# Planning for Package Deliveries in Risky Environments Over Multiple Epochs

Blake Wilson, Jeffrey Hudack and Shreyas Sundaram B. Wilson, and S. Sundaram
are with the Elmore Family School of Electrical and Computer Engineering,
Purdue University, West Lafayette, IN 47907 USA<EMAIL_ADDRESS>ye159<EMAIL_ADDRESS>Hudack is with the Air Force Research
Lab, Rome, NY 13441, USA<EMAIL_ADDRESS>
###### Abstract

We study a risk-aware robot planning problem where a dispatcher must construct
a package delivery plan that maximizes the expected reward for a robot
delivering packages across multiple epochs. Each package has an associated
reward for delivery and a risk of failure. If the robot fails while delivering
a package, no future packages can be delivered and the cost of replacing the
robot is incurred. The package delivery plan takes place over the course of
either a finite or an infinite number of epochs, denoted as the finite horizon
problem and infinite horizon problem, respectively. The dispatcher has to
weigh the risk and reward of delivering packages during any given epoch
against the potential loss of any future epoch’s reward. By using the ratio
between a package’s reward and its risk of failure, we prove an optimal,
greedy solution to both the infinite and finite horizon problems. The finite
horizon problem can be solved optimally in $O(Kn\log n)$ time where $K$ is the
number of epochs and $n$ is the number of packages. We show an isomorphism
between the infinite horizon problem and Markov Decision Processes to prove an
optimal $O(n)$ time algorithm for the infinite horizon problem.

##  I INTRODUCTION

Robotic platforms (such as drones) hold incredible promise for tasks such as
reconnaissance, search and rescue, and delivery of essential items in
dangerous environments (e.g., during natural disasters, or in battlefields).
In recent decades, significant focus has been put toward path planning for
robots by solving graph theoretic problems [6]. A common goal for these
problems is to collect rewards (e.g., information or objects) by visiting
physical locations. These problems are known as Orienteering Problems (OP) and
many variants are applicable to realistic engineering problems, such as
environmental inspection [5], multi-agent search [4], and sensor data
collection [3]. Typically, variants of OP are NP-Hard, and must be solved via
heuristics like Monte Carlo methods, and linear programming [2, 6, 7, 12]. Up
until recently, one aspect often missing from these formulations is that
robots come at a cost, and they face the risk of failure when deployed in
dangerous environments. Therefore, to maximize the effectiveness of a limited
supply of robots in such settings, one needs to weigh the reward of achieving
a given task against the risk of robot failure and cost of replacement.

To account for this, one can construct a variant of OP where each edge in the
graph has an associated risk of failure. Then, rather than finding a tour
which maximizes the collected reward, the goal becomes to find the tour that
maximizes the expected reward, i.e., risk-aware OP [4, 11]. These kinds of
problems are crucial for logistic operations in regions with adversaries, such
as maritime transportation [13]. Recently, it was shown that the solution to
some team risk-aware OP problems have a matroid structure which allow for
matroid optimization techniques [4]. However, if the problem introduces some
cyclic behavior like a return depot, then the cycles can break the matroid
structure and other optimization techniques are required [10]. The return
depot formulation encompasses many real-world applications like search and
rescue, sensor data collection, and package delivery.

In this paper, we focus on a particular OP where a single agent delivers
packages (e.g., containing aid or other essential items) from a depot to a set
of locations. Delivering a package to a given location earns a reward
(specific to that package and location), but also has a (location-specific)
risk of failure for the agent that is delivering the package. Furthermore,
packages are desired to be delivered to the various locations repeatedly
(i.e., over a set of epochs representing, for example, hours, days, or weeks).
Each epoch has the same set of packages as any other epoch. Multi-epoch
missions have been explored in the context of intermittent deployment [8, 9].
However, they have not been explored in the context of risk-aware task
allocation before. For each epoch, a dispatcher determines the order of
packages for the agent in order to maximize the expected reward from
delivering packages while accounting for risk of failure along the way. The
key challenge in this setting is to identify a rigorous strategy for
dispatching the agent that accounts for all of these various features (drone
costs, task-specific rewards, task-specific risks of failure, and the need to
plan over multiple epochs). Additionally, we will consider both a finite
horizon and an infinite horizon setting where the number of epochs is finite
and infinite, respectively. For the finite horizon case, we prove an optimal
$O(n\log n)$ time algorithm where $n$ is the number of packages. For the
infinite horizon case, we map the problem to an isomorphic Markov Decision
Process (MDP) and prove the optimal solution can be found in $O(n)$ time.

Our work differs from the previously mentioned studies in two main ways.
Firstly, insofar as we are aware, maximizing the expected reward across
multiple epochs has not been considered in any previous risk-aware OP variant.
Secondly, while the single-agent variant we consider in this paper does form a
matroid, our greedy solution is optimal without the need of matroid
heuristics.

##  II Problem Formulation

We consider time as being measured by a set of $K$ epochs
$\\{1,2,\ldots,K\\}$, where each epoch can represent an hour, a day, a week,
etc., as appropriate for the scenario. There is a depot $t_{0}$ which contains
a set of packages $\mathcal{T}=\\{t_{1},t_{2},...,t_{n}\\}$ at the start of
each epoch, where each package, $t_{i}\in\mathcal{T}$ is requested to be
delivered to a certain location. We assume that the package for each location
is unique (i.e., a package for one location cannot be delivered to another
location), and thus we use $t_{i}$ to denote both the package and the
destination location. Furthermore, we assume that the set of packages
$\mathcal{T}$ is replenished at the depot at the start of each epoch. Each
package $t_{i}\in\mathcal{T}$ has an associated reward
$r_{i}\in\mathbb{R}_{+}$ if it is successfully delivered to its target
location in a given epoch. An agent (e.g., drone) is available at the depot at
the first epoch to deliver the packages to their desired locations. Since the
agent may fail during an epoch in our problem formulation, for each
$h\in\\{1,2,...,K\\}$ we define $\alpha_{h}=1$, if the agent survives to epoch
$h$ and $\alpha_{h}=0$ otherwise. The agent can carry at most 1 package at a
time; after it has delivered the package it is carrying, it must return to the
depot to pick up another package. For each package $t_{j}$ that the agent
attempts to deliver, there is a probability that the agent will fail either en
route to the target location, or on the way back to the depot. We assume that
the events representing successful agent traversal of each leg of the trip are
independent and have equal probability, given by $\rho_{j}$ for some
$\rho_{j}\in[0,1]$. Thus the probability that the agent successfully delivers
package $t_{j}$ and returns to the depot is given by $\rho_{j}^{2}$. We also
assume that the events denoting successful agent traversal for different
packages are independent. If the agent fails while delivering a package, a
cost of $\theta\in\mathbb{R}_{\geq 0}$ is incurred and the agent cannot
deliver any more packages for the current or any future epoch.

During each epoch that the agent is alive it executes an assigned delivery
plan in some order specified by the dispatcher. Due to the fact that the agent
can only carry one package at a time, a package delivery plan for epoch $h$ is
represented by an ordered set of cycles
$\mathcal{C}_{h}=\\{W_{h,1},W_{h,2},...,W_{h,q_{h}}\\}$ where each package
delivery $W_{h,j}\in\mathcal{C}_{h}$ has the form
$W_{j}=\\{t_{0},t_{h,j},t_{0}\\}$, with $t_{h,j}\in\mathcal{T}$ representing
the $j$-th package being assigned for delivery by the agent in epoch $h$.

This ordered set may not contain every package delivery available for the
epoch if the dispatcher considers some packages too risky to deliver, i.e.
$q_{h}<|\mathcal{T}|$. Let
$\mathcal{C}=\\{\mathcal{C}_{1},\mathcal{C}_{2},\ldots,\mathcal{C}_{K}\\}$
denote a package delivery plan for the entire $K$-epoch period of the mission.
Let $E(\mathcal{C}_{h}|\alpha_{h})$ denote the expected reward provided by
plan $\mathcal{C}_{h}$ for epoch $h$ conditioned on whether the agent survives
to epoch $h$. The goal of the dispatcher is to maximize the expected reward
across all epochs by constructing a package delivery plan. By the law of total
expectation, the expected reward $E(\mathcal{C})$ across all epochs for a
given package delivery plan $\mathcal{C}$ is:

$E(\mathcal{C})=\sum_{h=1}^{K}E(\mathcal{C}_{h}|\alpha_{h}=1)P(\alpha_{h}=1).$
(1)

Then, the dispatcher’s goal is to solve the following problem:

######  Problem 1.

Risk-Aware Single-Agent Package Delivery (RSPD)

$\text{Find
}\text{arg}\max_{\mathcal{C}_{1},\ldots,\mathcal{C}_{K}}\sum_{h=1}^{K}E(\mathcal{C}_{h}|\alpha_{h}=1)P(\alpha_{h}=1).$
(2)

Consider the set of cycles
$\mathcal{C}_{h}=\\{W_{h,1},W_{h,2},\ldots,W_{q_{h}}\\}$ representing the
sequence of package deliveries assigned to the agent on epoch $h$. Assuming
the condition $\alpha_{h}=1$ (i.e., that the agent has survived to epoch $h$),
the conditional probability $\bar{\rho}_{h,j}$ that the agent completes a
given delivery $W_{h,j}\in\mathcal{C}_{h}$, and returns to base is dependent
on the probability the agent survives every cycle prior to and including
$W_{h,j}$, i.e.,
$\bar{\rho}_{h,j}=\rho_{h,1}^{2}\rho_{h,2}^{2}\cdots\rho_{h,j}^{2}$. Let
$\psi_{h,j}$ denote the probability that the agent successfully delivers the
$j$-th package in epoch $h$, given by
$\psi_{h,j}=\bar{\rho}_{h,j-1}\rho_{h,j}$. Then, the expected reward for
$W_{h,j}$ is given by $r_{h,j}\psi_{h,j}$. Additionally, $P(\alpha_{h}=1)$ is
dependent on the probability of finishing the last cycle for each epoch before
$h$. So for $h>1$, we can calculate $P(\alpha_{h}=1)$ by:

$P(\alpha_{h}=1)=\prod_{l=1}^{h-1}\bar{\rho}_{l,q_{l}}$ (3)

where $\bar{\rho}_{l,q_{l}}$ is the probability of finishing the last cycle
$W_{l,q_{l}}\in\mathcal{C}_{l}$. Because we are guaranteed the agent is alive
at the start of the first epoch, we have $P(\alpha_{1}=1)=1$. If the agent
survives to epoch $h$, the conditional expected reward for epoch $h$ is
calculated by:

$E(\mathcal{C}_{h}|\alpha_{h}=1)=\sum_{j=1}^{q_{h}}r_{h,j}\psi_{h,j}-\theta(1-\bar{\rho}_{h,q_{h}}).$
(4)

The first term captures the expected rewards of completing the ordered set of
tasks in epoch $h$, while the second term captures the expected cost of losing
the agent in epoch $h$. Substituting (3) into (2) reveals a telescopic
relationship:

$\displaystyle\sum_{h=1}^{K}E(\mathcal{C}_{h}|\alpha_{h}=1)P(\alpha_{h}=1)=E(\mathcal{C}_{1}|\alpha_{1}=1)+$
(5)
$\displaystyle\bar{\rho}_{1,q_{1}}\left(E(\mathcal{C}_{2}|\alpha_{2}=1)+\bar{\rho}_{2,q_{2}}(E(\mathcal{C}_{3}|\alpha_{3}=1)+\ldots)\right).$

Equation (5) can be written recursively as follows.

######  Definition 1 (Inductive Expected Reward for RSPD).

Given a package delivery plan
$\mathcal{C}=\\{\mathcal{C}_{1},\mathcal{C}_{2},\ldots,\mathcal{C}_{K}\\}$ for
RSPD, the reward functions $v_{1},v_{2},\ldots,v_{K}$ are defined recursively
as follows:

$\begin{split}v_{K}(\mathcal{C}_{K})&\triangleq
E(\mathcal{C}_{K}|\alpha_{K}=1)\\\ v_{h}(\mathcal{C}_{h})&\triangleq
E(\mathcal{C}_{h}|\alpha_{h}=1)+\bar{\rho}_{h,q_{h}}v_{h+1}(\mathcal{C}_{h+1})\end{split}$
(6)

for $h\in\\{1,2,\ldots,K-1\\}$.

This recursive relationship means we can maximize the total expected reward by
a Bellman equation that works backwards from epoch $K$:

$\displaystyle V_{h}$
$\displaystyle=\max_{\mathcal{C}_{h}}[E(\mathcal{C}_{h}|\alpha_{h}=1)+\bar{\rho}_{q_{h}}V_{h+1}],h\in\\{1,2,...,K-1\\}$
(7) $\displaystyle V_{K}$
$\displaystyle=\max_{\mathcal{C}_{K}}E(\mathcal{C}_{K}|\alpha_{K}=1).$ (8)

Now that we have the Bellman equation for solving RSPD, we will focus on the
characteristics of optimal package delivery plans that solve Equations (7) and
(8).

##  III Optimal Package Delivery Plans

For any given package delivery plan, the dispatcher decides which packages to
assign in each epoch and in what order. Naturally, when comparing two packages
$t_{i}$ and $t_{j}$, the dispatcher should pick the package with the highest
reward and the lowest probability of failure first, i.e., $r_{i}>r_{j}$ and
$\rho_{i}>\rho_{j}$. However, there will be many cases where $r_{i}>r_{j}$
while $\rho_{i}<\rho_{j}$, i.e., the most valuable packages are also the most
risky. Hence, the dispatcher needs to compare package deliveries by a function
of each package’s reward and its probability of failure. For each package
delivery, we will define its reward-to-risk ratio as follows, and later show
that it will serve as the primary means of comparison between packages.

######  Definition 2 (Reward-to-Risk Ratio).

Given a package delivery cycle $W_{j}=\\{t_{0},t_{j},t_{0}\\}$ for a package
$t_{j}\in T$, let the reward of the package be $r_{j}$ and the probability of
successfully delivering the package from the depot be $\rho_{j}$. We define
the reward-to-risk ratio of cycle $W_{j}$ as:

$\gamma_{j}\triangleq\frac{r_{j}\rho_{j}}{1-\rho_{j}^{2}}.$ (9)

The numerator captures the expected reward for delivering the package, and the
denominator captures the probability of the agent failing during the package
delivery cycle.

###  III-A Ordering of Cycles

Given a set of package deliveries, we first show that the dispatcher can
construct a package delivery plan for each epoch by ordering the packages by
their reward-to-risk ratios.

######  Lemma 1.

Consider the optimal package delivery plan for epoch $h$,
$\mathcal{C}_{h}^{*}=\\{W^{*}_{h,1},W^{*}_{h,2},\ldots,W^{*}_{h,q_{h}}\\}$.
Then, the package deliveries are in non-increasing order of their reward-to-
risk ratio, i.e. $\forall i<j:\gamma_{h,i}\geq\gamma_{h,j}$.

###### Proof.

By examining (7), we can see that the ordering of the deliveries does not
change $\bar{\rho}_{h,q_{h}}$ because the probability of finishing all the
cycles in epoch $h$ is a product of the probability of completing each cycle.
Therefore, we only need to prove that $E(\mathcal{C}_{h}|\alpha_{h}=1)$ is
maximized by ordering the cycles in non-increasing order of their reward-to-
risk ratios. We will prove this by contradiction. Consider an optimal plan
$\mathcal{C}^{*}_{h}=\\{W_{h,1},W_{h,2},...,W_{h,q_{h}}\\}$ and suppose
$\exists i\in\\{1,...,q_{h}-1\\}$ such that $\gamma_{h,i}<\gamma_{h,i+1}$.
Using (9), we have

$\displaystyle\frac{r_{h,i}\rho_{h,i}}{1-\rho^{2}_{h,i}}<\frac{r_{h,i+1}\rho_{h,i+1}}{1-\rho^{2}_{h,i+1}}.$

Which further implies,

$\displaystyle
r_{h,i}\rho_{h,i}+r_{h,i+1}\rho_{h,i+1}\rho^{2}_{h,i}<r_{h,i+1}\rho_{h,i+1}+r_{h,i}\rho_{h,i}\rho^{2}_{h,i+1}.$
(10)

Now define $\mathcal{C}_{h}$ to be the same as $\mathcal{C}^{*}_{h}$ except
with the packages in positions $i$ and $i+1$ swapped. Define
$\bar{\psi}_{h,i}$ and $\bar{\psi}_{h,i+1}$ to be the probability of receiving
rewards $r_{h,i}$ and $r_{h,i+1}$ in the ordering of $\mathcal{C}_{h}$. Then,

$\displaystyle E(\mathcal{C}_{h}|$
$\displaystyle\alpha_{h}=1)-E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)=$ (11)
$\displaystyle\sum_{k=0}^{i-1}r_{h,k}\psi_{h,k}+r_{h,i+1}\bar{\psi}_{h,i+1}+r_{h,i}\bar{\psi}_{h,i}$
$\displaystyle+\sum_{k=i+2}^{q_{h}}r_{h,k}\psi_{h,k}-\theta(1-\bar{\rho}_{h,q_{h}})$
$\displaystyle-\sum_{k=0}^{i-1}r_{h,k}\psi_{h,k}-r_{h,i}\psi_{h,i}-r_{h,i+1}\psi_{h,i+1}$
$\displaystyle-\sum_{k=i+2}^{q_{h}}r_{h,k}\psi_{h,k}+\theta(1-\bar{\rho}_{h,q_{h}}).$

Using the definition of $\psi_{h,i}$ and the ordering of $W_{h,i}$ and
$W_{h,i+1}$ in $\mathcal{C}_{h}$, we know that
$\bar{\psi}_{h,i+1}=\rho_{h,i+1}\bar{\rho}_{h,i-1}$ and
$\bar{\psi}_{h,i}=\rho_{h,i}\rho_{h,i+1}^{2}\bar{\rho}_{h,i-1}$. Thus,

$\displaystyle E(\mathcal{C}_{h}|$
$\displaystyle\alpha_{h}=1)-E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)=$
$\displaystyle
r_{h,i+1}{\rho_{h,i+1}}\bar{\rho}_{h,i-1}+r_{h,i}{\rho_{h,i}}{\rho_{h,i+1}^{2}}\bar{\rho}_{h,i-1}$
$\displaystyle-$ $\displaystyle
r_{h,i}{\rho_{h,i}}\bar{\rho}_{h,i-1}-r_{h,i+1}{\rho_{h,i+1}}\rho^{2}_{h,i}\bar{\rho}_{h,i-1}.$
(12)

By factoring out $\bar{\rho}_{h,i-1}$ from all the terms and using (10) in
(12), one can see that
$E(\mathcal{C}_{h}|\alpha_{h}=1)-E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)>0$ which
contradicts the optimality of $\mathcal{C}^{*}_{h}$.

∎

Next, we provide a pair of results that specify exactly which packages should
be included in the package delivery plan for each epoch.

######  Lemma 2.

Consider the optimal package delivery plan $\mathcal{C}^{*}_{h}$ that
maximizes the Bellman equation (7) for epoch $h$. If the reward-to-risk ratio
$\gamma^{\prime}$ for package $t^{\prime}\in T$ satisfies the following
inequality, then it will be included in the optimal plan
$\mathcal{C}^{*}_{h}$:

$\gamma^{\prime}>\theta+V_{h+1}.$ (13)

###### Proof.

We will prove this by contradiction. Suppose $t^{\prime}$ is not included in
the optimal plan $\mathcal{C}^{*}_{h}$. Then, the value function (7) for
$\mathcal{C}^{*}_{h}$ is

$V_{h}^{*}=\sum_{W_{h,i}\in\mathcal{C}^{*}_{h}}r_{h,i}\psi_{h,i}+\bar{\rho}_{h,q_{h}}V_{h+1}-\theta(1-\bar{\rho}_{h,q_{h}}).$

Now, let $V^{\prime}_{h}$ be the accumulated reward if the delivery cycle
$W^{\prime}$ for $t^{\prime}$ is included in $\mathcal{C}^{*}_{h}$. Let
$r^{\prime}$ and $\rho^{\prime}$ be the reward and probability of success for
delivering $t^{\prime}$ (and returning), respectively. We relax the ordering
of the packages so that $t^{\prime}$ is delivered after all packaged in
$\mathcal{C}^{*}_{h}$. By doing this, Lemma 1 guarantees this ordering is a
lower bound on $V^{\prime}_{h}$. We have

$V^{\prime}_{h}\geq\sum_{W_{h,i}\in\mathcal{C}^{*}_{h}}r_{h,i}\psi_{h,i}+r^{\prime}\psi^{\prime}+\rho^{\prime}\bar{\rho}_{h,q_{h}}V_{h+1}-\theta(1-\rho^{\prime}\bar{\rho}_{h,q_{h}}).$

Subtracting the value function for $\mathcal{C}^{\prime}_{h}$ gives us

$\displaystyle V^{\prime}_{h}-V^{*}_{h}$ $\displaystyle\geq
r^{\prime}{\rho^{\prime}}\bar{\rho}_{h,q_{h}}+(V_{h+1}+\theta)(({\rho^{\prime}})^{2}\bar{\rho}_{h,q_{h}}-\bar{\rho}_{h,q_{h}})$
(14)
$\displaystyle=\bar{\rho}_{h,q_{h}}(\frac{r^{\prime}{\rho^{\prime}}}{(1-(\rho^{\prime})^{2})}-V_{h+1}-\theta)(1-(\rho^{\prime})^{2}).$
(15)

By applying Definition 9 to (13) we obtain

$\frac{r^{\prime}{\rho^{\prime}}}{(1-(\rho^{\prime})^{2})}>V_{h+1}+\theta.$
(16)

But, applying (16) to (15) implies that $V^{\prime}_{h}-V^{*}_{h}>0$ which
contradicts the optimality of $\mathcal{C}^{*}_{h}$.

∎

The derivations in the above lemma also show that including any task whose
reward-to-risk ratio is equal to $\theta+V_{h+1}$ will not affect $V_{h}$. We
now show which tasks will be excluded from the optimal plan.

######  Lemma 3.

Any package delivery whose reward-to-risk ratio does not satisfy Lemma 2 is
not included in the optimal package delivery plan for epoch $h$, i.e.,

$\gamma^{\prime}<\theta+V_{h+1}.$ (17)

###### Proof.

By Lemma 2, $\mathcal{C}^{*}_{h}$ should contain all packages in $\mathcal{T}$
whose reward-to-risk ratio does not satisfy (17). By applying Lemma 1, any
package $t^{\prime}$ whose $\gamma^{\prime}$ satisfies (17) will be placed
after all package deliveries in $\mathcal{C}^{*}_{h}$. Then, by following a
similar proof as in Lemma 2, it is easy to see that $V_{h}$ decreases by
adding $t^{\prime}$ to $\mathcal{C}^{*}_{h}$. ∎

######  Corollary 1.

By consequence of Lemma 2 and Lemma 3, the optimal expected reward $V_{h}$ for
epoch $h$ is obtained by the dispatcher assigning all packages whose reward-
to-risk ratio satisfies (13) and ordering them by non-increasing reward-to-
risk ratio when calculating $\mathcal{C}^{*}_{h}$, i.e.,

$\displaystyle\mathcal{C}^{*}_{h}=\\{W_{h,1},W_{h,2},...,W_{h,q_{h}}|\gamma_{h,1}\geq...\geq\gamma_{h,q_{h}}>\theta+V_{h+1}\\}$

######  Corollary 2.

The package delivery plan for epoch $h$ is always a subset of the package
delivery plan for epoch $h+1$, i.e.,

$\forall h\in\\{1,2,...,K-1\\},\mathcal{C}_{h}\subseteq\mathcal{C}_{h+1}.$

Using Corollary 1 and Corollary 2, we construct Algorithm 1 to find the
optimal solution to RSPD. Algorithm 1 finishes in $O(n\log n)$ time because
sorting the packages by their reward-to-risk ratio requires only $O(n\log n)$.
The while loop in line 1 can be accomplished in $O(n)$ time instead of $O(Kn)$
time by using Corollary 2 to construct package delivery plans from the indices
in $\mathcal{T}$ instead of copying packages for each iteration.

Input: An instance of RSPD

Result: Optimal $\mathcal{C}$ that solves RSPD

1 for  _$t_{i}\in T$_ do

2 $W_{i}=\\{t_{0},t_{i},t_{0}\\}$;

3 Calculate $\gamma_{i}$ for $W_{i}$ using equation (9) in Definition 9;

4 end for

5Let $\mathcal{C}_{K}$ be the ordered set of all package deliveries $W_{i}$
such that $\gamma_{i}>\theta$ and the package deliveries are in non-increasing
order of $\gamma_{i}$;

6 Calculate $V_{K}$ using (4) and (8) with $\mathcal{C}_{K}$;

7 $h=K-1$;

8

9while  _$h\neq 0$ _ do

10 Let $\mathcal{C}_{h}$ be the ordered set of all package deliveries $W_{i}$
where $\gamma_{i}>V_{h+1}+\theta$ (non-increasing order of $\gamma_{i}$) ;

11 Calculate $V_{h}$ using (4) and (7) with $\mathcal{C}_{h}$;

12 $h=h-1$;

13

14 end while

Algorithm 1 Optimal Solution to RSPD

We also note here that the above results (other than Corollary 2) would also
hold if the set of package delivery plans changed at each epoch. This is shown
by the following corollary.

######  Corollary 3.

Consider an instance of RSPD where each epoch $h$ has a unique set of packages
$\mathcal{T}_{h}$ available for delivery. Then, Algorithm 1 calculates the
optimal package delivery plan in time $Kn+O(n\log n)$.

###### Proof.

Note that Lemmas 1-3 and Corollary 1 still hold for heterogeneous epochs.
However, we cannot use Corollary 2 to remove the $K$ dependence on the time
complexity. Analyzing Algorithm 1 with slight modifications to account for
heterogeneous epochs and without using Corollary 2 gives a time complexity of
$Kn+O(n\log n)$. ∎

###  III-B Infinite Horizon Package Delivery

Up until now we have only considered finite duration missions that are
guaranteed to end. However, there may be scenarios where the dispatcher cannot
assume the mission will ever end (e.g., logistics companies). We will now
define an instance of RSPD with an infinite number of epochs and provide an
optimal solution to the problem.

######  Problem 2 (Infinite Horizon RSPD (IHRSPD)).

Consider an instance of RSPD with an infinite number of epochs. Then, the
problem is to maximize the following expected reward:

$\text{Find
}\text{arg}\max_{\mathcal{C}_{1},\mathcal{C}_{2},\ldots}\sum_{h=1}^{\infty}E(\mathcal{C}_{h}|\alpha_{h}=1)P(\alpha_{h}=1).$
(18)

Despite being an infinite sum, we can show that every package delivery plan
for an instance of IHRSPD has a finite expected reward.

######  Lemma 4.

Every instance of IHRSPD has a finite expected reward.

###### Proof.

Consider any package delivery plan $\mathcal{C}$ whose expected reward is:

$E(\mathcal{C})=\sum_{h=1}^{\infty}E(\mathcal{C}_{h}|\alpha_{h}=1)P(\alpha_{h}=1).$
(19)

First, note that if the plan $\mathcal{C}$ only specifies package deliveries
for a finite number of epochs, then the expected reward is trivially finite.
Thus, we focus on plans $\mathcal{C}$ that specify deliveries over an infinite
number of epochs.

If for any $\mathcal{C}_{h}\in\mathcal{C}$, $\mathcal{C}_{h}=\emptyset$, then
$E(\mathcal{C}_{h}|\alpha_{h}=1)=0$ and $P(\alpha_{h+1}=1|\alpha_{h}=1)=1$.
This implies that the infinite summation (19) does not change if we remove
$\mathcal{C}_{h}$ from $\mathcal{C}$ when $\mathcal{C}_{h}=\emptyset$.
Therefore, we can restrict attention to plans $\mathcal{C}$ which are composed
of non-empty package delivery plans for each epoch.

The dispatcher can only choose from a finite number of non-empty package
delivery plans for each epoch $h$, i.e., $\mathcal{C}_{h}\in 2^{\mathcal{T}}$.
By (4), the set of all possible values $\mathcal{E}_{h}$ for the expected
reward $E(\mathcal{C}_{h}|\alpha_{h}=1)$ during epoch $h$ is also finite and
this set does not change with each epoch, i.e.,
$\mathcal{E}_{1}=\mathcal{E}_{2}=...$. By the same argument, the set of
possible probabilities of success $\xi_{h}$ for epoch $h$ also has a finite
size and does not change with each epoch. Suppose we knew both the package
delivery plan $\mathcal{C}^{*}_{h}\in 2^{\mathcal{T}}$ that maximizes
$E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)$ such that $\forall\mathcal{C}_{h}\in
2^{\mathcal{T}},E(\mathcal{C}_{h}|\alpha_{h}=1)\leq
E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)$ and the package delivery plan
$\mathcal{C}^{\prime}_{h}$ that maximizes the probability of success
$\rho^{\prime}$ such that $\forall\rho\in\xi_{h},\rho\leq\rho^{\prime}<1$.

For every $\mathcal{C}_{h}\in\mathcal{C}$, the expected reward
$E(\mathcal{C}_{h}|\alpha_{h}=1)\leq E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)$.
Likewise, for every $\mathcal{C}_{h}\in\mathcal{C}$,
$P(\alpha_{h}=1|\alpha_{h-1}=1)\leq\rho^{\prime}$. By swapping
$E(\mathcal{C}_{h}|\alpha_{h}=1)$ for every epoch
$E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)$ in (19) along with swapping
$P(\alpha_{h}=1|\alpha_{h-1}=1)$ for $\rho^{\prime}$ in every epoch when
computing $P(\alpha_{h}=1)$ in (19), we obtain the following upper bound on
(19) for any package delivery plan $\mathcal{C}$:

$E(\mathcal{C})\leq\frac{E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)}{1-\rho^{\prime}}<\infty.$

∎

Now that we have shown that every instance of IHRSPD has a finite expected
reward, we will introduce the Markov Decision Process (MDP) formalism to prove
that the optimal package delivery plan is stationary. To show this, we will
define a MDP isomorphic to an instance of IHRSPD. Then, using the main result
from [1], we will show that the optimal expected reward for the MDP and IHRSPD
requires choosing the same package delivery plan for each epoch, i.e., a
stationary package delivery plan. Now, we provide the following MDP formalism
which will likely extend beyond IHRSPD and into many other variations of
multi-epoch risk aware task allocation problems.

######  Definition 3 (Markov Decision Process).

A Markov Decision Process (MDP) is specified by the set
$H=(S,A,\\{A(x)\\},R,P)$ composed of the following structures. The state-space
$S$ is a denumerable set, i.e., at most bijective to the natural numbers
$\mathbb{N}$. The action set $A$ is a metric space containing all possible
actions for every state $x\in S$. For each state $x\in S$, there exists a
compact, action set $A(x)\subset A$ of possible actions while in state $x$.
$R$ is a reward function defined for each pair of states and actions
$\\{(x,\mathbf{a})|x\in S,\mathbf{a}\in A(x)\\}$. Finally, the control
transition probabilities are specified by a probability function
$P=[p_{xy}(\cdot)]$ that defines the probability of transitioning from state
$x\in S$ to state $y\in S$, under a given action.

Every MDP begins in an initial state $X_{0}$ and progresses to future states
in the following manner. Given any current state $X_{h}=x\in S$, a controller
follows some policy $\pi$ that specifies a desired action $A_{h}=\pi(X_{h}=x)$
based on the current epoch $h$ and the state $X_{h}$. Then, a reward
$R(X_{h},A_{h})$ is earned and the state transitions to a new state
$X_{h+1}=y\in S$ with probability $p_{xy}(A_{h})$. This process repeats
indefinitely. Given that this process proceeds indefinitely, if we consider
all possible policies $\mathcal{P}$ for a fixed set of reward and probability
functions, then there exists an expected reward for every policy
$\pi\in\mathcal{P}$ over an infinite horizon.

######  Definition 4 (Expected Total Reward for Infinite-Horizon MDP).

Consider a MDP and some policy $\pi$. Then, the expected total reward for the
MDP beginning at state $X_{0}=x\in S$ under policy $\pi$ is defined as:

$V(x,\pi)=E^{\pi}_{x}\left[\sum_{h=1}^{\infty}R(X_{h},A_{h})\right].$ (20)

We will construct an isomorphic MDP by following the definition of IHRSPD.
Firstly, the agent begins in an alive state $x_{s}$ and the dispatcher chooses
a combination of packages for the agent to deliver while alive. To capture
this behavior, construct a MDP whose initial state $x_{s}$ corresponds to the
agent being alive. While the agent is in the alive state, the dispatcher
chooses a combination of packages from the set of all packages $\mathcal{T}$.
This choice is captured by a policy $\pi$ choosing an action vector
$\mathbf{a}$ from the action space $A$, where $A$ is the set of all n-bit
strings $A=\\{0,1\\}^{n}$ and $n=|\mathcal{T}|$ is the number of tasks in the
instance of IHRSPD. For each action vector $\mathbf{a}\in A$, the dispatcher
treats each component $a_{i}$ of $\mathbf{a}\in A$ as a bit that determines if
package $t_{i}\in\mathcal{T}$ is taken for the current epoch $h$. We can
define $\mathcal{C}_{h}$ to be the associated package delivery plan for action
vector $\mathbf{a}=A_{h}$ where the order of the deliveries is given by Lemma
1. Given that the agent attempts to deliver the packages in $\mathcal{C}_{h}$,
there exists $|\mathcal{C}_{h}|+1$ chances for the agent to fail in between
receiving rewards, i.e., before the first package delivery, between any two
package deliveries, or after the last package delivery. Furthermore, given the
action vector $\mathbf{a}$, we define the set $\mathcal{F}(\mathbf{a})$ as the
set of all n-bit strings that specify the subsets of packages the agent
delivered before failure. Then, for each chance of failing, we specify a state
$x_{0,\mathbf{f}}$ where $\mathbf{f}\in\mathcal{F}(\mathbf{a})$ specifies the
subset of packages the agent was able to deliver before failure. Then, the
probability of delivering only the subset of packages specified by
$\mathbf{f}$ given the agent attempted to deliver all the packages specified
by $\mathbf{a}$ can be captured by a probability function
$\phi(\mathbf{f}|\mathbf{a})$.

For all $\mathbf{f}\in\mathcal{F}(\mathbf{a})$ such that
$\mathbf{f}\neq\mathbf{a}$, let $W_{j}$ be the last package completed by the
agent before failing as specified by $\mathbf{f}$. Then,
$\phi(\mathbf{f}|\mathbf{a})=\psi_{j}(1-\rho_{j}\rho_{j+1})=\psi_{j}-\psi_{j+1}$
where $\psi_{j}$ is the probability of completing cycle $W_{j}$ and $\rho_{j}$
and $\rho_{j+1}$ are the probabilities of successfully traversing between
$t_{j}$ and the depot, and traversing between the depot and $t_{j+1}$,
respectively. If $\mathbf{f}=\mathbf{0}$, then
$\phi(\mathbf{f}|\mathbf{a})=(1-\rho_{1})$ where $\rho_{1}$ is the probability
of delivering the first package specified by $\mathbf{a}$. However, if
$\mathbf{f}=\mathbf{a}$, then
$\phi(\mathbf{f}|\mathbf{a})=\psi_{q_{h}}(1-\rho_{q_{h}})$ where
$\psi_{q_{h}}$ is the probability of delivering the last package $t_{q_{h}}$
and $(1-\rho_{q_{h}})$ is the probability of failing between $t_{q_{h}}$ and
the depot. Naturally, if $\mathbf{f}\not\in\mathcal{F}(\mathbf{a})$, then
$\phi(\mathbf{f}|\mathbf{a})=0$. For the case where the agent delivers all the
packages and returns to the depot, we specify the state $x_{1,\mathbf{a}}$ and
the probability $\bar{\rho}_{\mathbf{a}}=\bar{\rho}_{q_{h}}$ where
$\bar{\rho}_{q_{h}}$ is the probability of finishing the last cycle
$W_{q_{h}}$ and returning to the depot.

######  Definition 5 (MIHRSPD Transition Probability Functions).

For all $\mathbf{a}\in A$ and $\mathbf{f}\in\mathcal{F}(\mathbf{a})$,

$p_{x_{s},x_{0,\mathbf{f}}}(\mathbf{a})=\phi(\mathbf{f}|\mathbf{a})$
$p_{x_{s},x_{1,\mathbf{a}}}=\bar{\rho}_{\mathbf{a}}$
$p_{x_{0,\mathbf{f}},x_{d}}=p_{x_{1,\mathbf{a}},x_{s}}=1.$

For all other combinations of states $x,y\in S$,

$p_{x,y}=0.$

Using the same conventions, we can construct reward functions given different
outcomes in IHRSPD. Namely, if the agent fails while delivering the packages
specified by $\mathbf{a}$, then it will receive a partial reward dependent on
$x_{0,\mathbf{f}}$. Namely, it will receive the sum of all rewards for the
packages it was able to deliver, but then incur a cost $\theta$ for failure.
Likewise, if the agent does not fail, i.e., $X_{h}=x_{1,\mathbf{f}}$, then it
will receive the sum of all rewards for the packages specified by $\mathbf{f}$
and return to the alive state $x_{s}$. This is captured by the following
reward functions.

######  Definition 6 (MIHRSPD Reward Functions).

For all $\mathbf{a}\in A$ and $\mathbf{f}\in\mathcal{F}(\mathbf{a})$,

$R(x_{0,\mathbf{f}})=\sum_{f_{j}\in\mathbf{f}:f_{j}=1}r_{j}-\theta$
$R(x_{1,\mathbf{f}})=\sum_{f_{j}\in\mathbf{f}:f_{j}=1}r_{j}.$

For all other states $x\in S$,

$R(x)=0.$

Given these probability and reward functions, we can properly define the
following MDP which is isomorphic to IHRSPD by definition.

######  Definition 7 (Markov-IHRSPD (MIHRSPD)).

An instance of MIHRSPD is given by the set $\mathcal{M}=\\{\mathcal{I},H\\}$
where $\mathcal{I}$ is an instance of IHRSPD and $H=(S,A,\\{A(x)\\},R,P)$ is a
MDP defined as follows. Define the state-space
$S=\\{x_{s},x_{d}\\}\cup\\{x_{i}|\forall i\in\\{0,1\\}\times
2^{\mathcal{T}}\\}$. Let the action space $A$ be the set of all n-bit strings
$A=\\{0,1\\}^{n}$, where $n$ is the number of tasks $|\mathcal{T}|$ in
$\mathcal{I}$. Define the compact action spaces $\forall x\in S:A(x)=A$. Let
the reward functions and probability transition functions be specified by
$\mathcal{I}$ using Definition 6 and Definition 5. Then, the problem is to
find a policy $\pi$ in the set of all policies $\mathcal{P}$ that solves

$\text{Find
}\text{arg}\max_{\pi\in\mathcal{P}}E^{\pi}_{x}\left[\sum_{h=1}^{\infty}R(X_{h},A_{h})\right].$
(21)

Using the main result from [1], if the MDP in Definition 21 satisfies three
simple properties, and every policy has a finite expected reward, i.e.,
$\forall x\in S$ and $\forall\pi\in\mathcal{P}\implies V(x,\pi)<\infty$, then
the optimal policy is stationary, i.e., $\forall h\geq 0,\forall x\in
S:X_{h}=X_{h+1}\implies\pi^{*}(X_{h})=\pi^{*}(X_{h+1})$.

######  Theorem 1 (Existence of Stationary Policies [1]).

Consider a MDP satisfying the following conditions.

  1. 1.

For each $x,y\in S$, the mapping $a\mapsto p_{xy}(a)$ is continuous in $a\in
A(x)$.

  2. 2.

For each $x\in S$, $a\mapsto R(x,a)\in[-\infty,\infty)$ is an upper
semicontinuous function of $a\in A(x)$

  3. 3.

The number of positive recurrent classes $\mathbf{N}^{\tau}$ is a continuous
function of $\tau\in\mathbb{F}$ where $\mathbb{F}$ is the set of all
stationary policies.

Then, there exists an optimal stationary policy $\pi^{*}$ that maximizes (20),
i.e., $\forall h\geq 0,\forall x\in
S:X_{h}=X_{h+1}\implies\pi^{*}(X_{h})=\pi^{*}(X_{h+1})$.

A positive recurrent class, as mentioned in Requirement 3 of Theorem 1, is a
set of states which will continually be revisited throughout the MDP.
Requirement 3 is satisfied if every stationary policy for a given MDP has a
continuous number of positive recurrent classes. In the case of MIHRSPD, the
number of recurrent classes is constant, i.e., $\mathbf{N}^{\tau}=1$. We will
prove $\mathbf{N}^{\tau}=1$ in the following lemma and apply Theorem 1 to show
the optimal policy is stationary.

######  Lemma 5.

By Theorem 1, the optimal policy for an instance of MIHRSPD is stationary.

###### Proof.

Consider an instance $\mathcal{M}=\\{\mathcal{I},H\\}$ of MIHRSPD constructed
from $\mathcal{I}$. One can easily verify that the reward functions in
Definition 6, and the probability transition laws in Definition 5 are
continuous functions over $A$, which satisfies Requirements 1 and 2 of Theorem
1. For Requirement 3, if the agent attempts to take any positive number of
packages as its stationary policy, i.e., $\mathbf{a}\neq\mathbf{0}$, the agent
will eventually fail to deliver all its packages and transition to a state
$x_{0,\mathbf{f}}$. After staying in the state $x_{0,\mathbf{f}}$ for one
epoch, the state will automatically transition to the failure state, $x_{d}$,
where the MDP will stay forever. Therefore, $x_{d}$ is considered both an
absorbing state and a recurrent state because a given subset of actions will
always eventually transition the state to $x_{d}$ (absorbing) and stay in the
state forever (recurrent). Likewise, if the action vector
$\mathbf{a}=\mathbf{0}$ is always chosen as the stationary policy, then
$x_{s}$ can also be considered an absorbing and recurrent state because the
probability of transitioning back to $x_{s}$ is $1$. Then, for any given
stationary policy, the number of recurrent classes $\mathbf{N}^{\tau}=1$.
Finally, using a similar proof as in Lemma 4, one can show that the expected
reward for $\mathcal{M}$ is finite because $\mathcal{M}$ is isomorphic to
$\mathcal{I}$. Therefore, MIHRSPD will always satisfy Theorem 1, which implies
the optimal policy is stationary. ∎

######  Corollary 4.

The optimal package delivery plan $\mathcal{C}$ for an instance of IHRSPD is
stationary, i.e.,
$\forall\mathcal{C}_{h}\in\mathcal{C}:\mathcal{C}_{h}=\mathcal{C}_{h+1}$.

###### Proof.

By Lemma 5, the optimal policy for a MDP $\mathcal{M}$ constructed from
instance of IHRSPD $\mathcal{I}$ is stationary. Because $\mathcal{M}$ is by
definition isomorphic to $\mathcal{I}$, the optimal package delivery plan for
$\mathcal{I}$ is stationary. ∎

Given we know the optimal package delivery plan is stationary, we will now
find the optimal stationary package delivery plan. To do this, we extend the
notion of reward-to-risk ratio to apply to package delivery plans using epoch
risk ratios.

######  Definition 8 (Epoch Risk Ratio).

Given a package delivery plan $\mathcal{C}_{h}$ for epoch $h$ during an
instance of RSPD or IHRSPD, let $\bar{\rho}_{q_{h}}$ be the probability of
finishing the last cycle $W_{q_{h}}$ in $\mathcal{C}_{h}$. Then, we denote the
epoch risk ratio for $\mathcal{C}_{h}$ as $\epsilon_{h}$ and compute it by:

$\epsilon_{h}=\frac{E(\mathcal{C}_{h}|\alpha_{h}=1)}{1-\bar{\rho}_{q_{h}}}$

Given the package delivery plan is stationary, the following lemma
characterizes the expected reward using the epoch risk ratio.

######  Lemma 6.

Consider an instance of IHRSPD with a stationary package delivery plan, i.e.,
$\mathcal{C}_{1}=\mathcal{C}_{2}=\ldots$. Then, the expected reward for IHRSPD
is given by the epoch risk ratio for the package delivery plan for any epoch
$\mathcal{C}_{h}$:

$\frac{E(\mathcal{C}_{h}|\alpha_{1}=1)}{1-\bar{\rho}_{q_{h}}}.$

###### Proof.

Because the package delivery plans for each epoch are equal,
$\mathcal{C}_{1}=\mathcal{C}_{2}=\ldots$, the expected reward for each epoch
(4) will also be equal, i.e.,
$E(\mathcal{C}_{1}|\alpha_{1}=1)=E(\mathcal{C}_{2}|\alpha_{2}=1)=\ldots$.
Furthermore, the last cycles in each package delivery plan will also be equal
$q_{1}=q_{2}=...=p$ for some $p$. By applying the same assumption to (3), we
can see that
$P(\alpha_{h}=1)=(\bar{\rho}_{q_{h}})^{h-1}=(\bar{\rho}_{p})^{h-1}$. Given
(18), we can factor out the expectation $E(\mathcal{C}_{1}|\alpha_{1}=1)$ from
every epoch and rewrite (18) to be a geometric series which yields the epoch
risk ratio. More specifically, we have

$\displaystyle\sum_{h=1}^{\infty}E(\mathcal{C}_{h}|\alpha_{h}=1)P(\alpha_{h}=1)$
$\displaystyle=E(\mathcal{C}_{1}|\alpha_{1}=1)\sum_{h=1}^{\infty}(\bar{\rho}_{p})^{(h-1)}$
$\displaystyle=\frac{E(\mathcal{C}_{1}|\alpha_{1}=1)}{1-\bar{\rho}_{p}}.$

∎

######  Lemma 7.

The epoch risk ratio $\epsilon_{h}$ for a package delivery plan
$\mathcal{C}_{h}$ during epoch $h$ is maximal when
$\mathcal{C}_{h}=\\{W_{\text{max}}\\}$ where $W_{\text{max}}$ is the package
delivery with the maximal epoch risk ratio, $\epsilon_{\text{max}}$.

###### Proof.

We will prove this by contradiction. Consider the optimal package delivery
plan $\mathcal{C}^{*}_{h}$ whose epoch risk ratio is greater than
$\epsilon_{\text{max}}$. However, for each individual package delivery in
$W_{i}\in\mathcal{C}^{*}_{h}$, its reward-to-risk ratio is less than
$\gamma_{\text{max}}$ (the largest reward-to-risk ratio for any individual
task). This implies

$\displaystyle\frac{E(\mathcal{C}^{*}_{h}|\alpha_{h}=1)}{1-\bar{\rho}_{q_{h}}}$
$\displaystyle>\frac{E(\mathcal{C}_{h}|\alpha_{h}=1)}{1-(\rho_{1})^{2}}$
$\displaystyle\Rightarrow\frac{\sum_{i}{r_{i}\psi_{i}}}{1-\bar{\rho}_{q_{h}}}$
$\displaystyle>\frac{r_{1}\rho_{1}}{1-(\rho_{1})^{2}}$
$\displaystyle\Rightarrow\sum_{i}{r_{i}\psi_{i}}+r_{1}\rho_{1}\bar{\rho}_{q_{h}}$
$\displaystyle>r_{1}\rho_{1}+\sum_{i}{r_{i}\psi_{i}}(\rho_{1})^{2}.$ (22)

Inequality (22) claims that the expected reward for a package delivery plan
where $W_{\text{max}}$ is delivered after all packages in
$\mathcal{C}^{*}_{h}$ is optimal compared to delivering $W_{\text{max}}$
before all packages in $\mathcal{C}^{*}_{h}$. However, if $W_{\text{max}}$ has
a higher reward-to-risk ratio than any package in $\mathcal{C}^{*}_{h}$, then
Lemma 1 proves this is suboptimal. ∎

######  Corollary 5.

By an extension of Lemma 7, the optimal stationary package delivery plan
$\mathcal{C}$ that solves an instance $\mathcal{I}$ of IHRSPD is given by
$\mathcal{C}=\\{\forall h>0:\mathcal{C}_{h}=\\{W_{\text{max}}\\}\\}$ where
$W_{\text{max}}$ is the package delivery with highest reward-to-risk ratio in
$\mathcal{I}$.

The above result shows that in the case of the infinite horizon package
delivery problem, the optimal strategy is to deliver only the most valuable
package in each epoch. Thus, one can easily construct an $O(n)$ time algorithm
to solve IHRSPD by searching for the package with greatest reward-to-risk
ratio.

##  IV CONCLUSIONS AND FUTURE WORK

In this work, we formulate the Risk-Aware Single Agent Delivery (RSPD) problem
where a dispatcher assigns package deliveries to a single agent based on both
the reward associated with the package and the probability of successfully
surviving the delivery. If the agent fails mid-delivery, a cost is incurred
and the agent cannot make future deliveries. Therefore, the dispatcher must
weigh the reward from a delivery against the loss of all future rewards across
multiple epochs of the problem. We solve variants of this problem, one where
there is a finite number of epochs (finite horizon) and one where there is an
infinite number of epochs (infinite horizon). For the finite horizon case, we
provide an optimal algorithm with time-complexity $O(n\log n)$. For the
infinite horizon problem, we construct an isomorphic Markov Decision Process
(MDP) to prove the optimal package delivery plan is to deliver the same
package forever. Finding the optimal solution to the infinite horizon case
only takes $O(n)$ time. Leveraging this connection to address multi-agent
variants of our problem may be of interest for future work.

##  V ACKNOWLEDGMENTS

We would like to acknowledge Lintao Ye for helpful discussions on greedy
algorithms.

## References

  * [1] R. Cavazos-Cadena, E. A. Feinberg, and R. Montes-De-Oca.  A note on the existence of optimal policies in total reward dynamic programs with compact action sets.  Mathematics of Operations Research, 25(4):657–666, 2000.
  * [2] A. Gunawan, H. C. Lau, and P. Vansteenwegen.  Orienteering problem: A survey of recent variants, solution approaches and applications.  European Journal of Operational Research, 255(2):315–332, 2016\.
  * [3] J. Hudack.  Risk-aware planning for sensor data collection.  Dissertations - All, 582, 2016.
  * [4] S. Jorgensen, R. H. Chen, M. B. Milam, and M. Pavone.  The matroid team surviving orienteers problem: Constrained routing of heterogeneous teams with risky traversal, 2017.
  * [5] J. Katrasnik, F. Pernus, and B. Likar.  A survey of mobile robots for distribution power line inspection.  IEEE Transactions on Power Delivery, 25(1):485–493, 2010.
  * [6] G. Laporte.  The vehicle routing problem: An overview of exact and approximate algorithms.  European Journal of Operational Research, 59(3):345–358, 1992.
  * [7] G. Laporte and S. Martello.  The selective travelling salesman problem.  Discrete Applied Mathematics, 26(2):193–207, 1990.
  * [8] J. Liu and R. K. Williams.  Submodular optimization for coupled task allocation and intermittent deployment problems.  IEEE Robotics and Automation Letters, 4(4):3169–3176, 2019.
  * [9] J. Liu and R. K. Williams.  Monitoring over the long term: Intermittent deployment and sensing strategies for multi-robot teams.  In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 7733–7739, 2020.
  * [10] A. Prasad, J. Hudack, and S. Sundaram.  On optimal policies for risk-aware sensor data collection by a mobile agent.  IFAC-PapersOnLine, 52(20):321–326, 2019.  8th IFAC Workshop on Distributed Estimation and Control in Networked Systems NECSYS 2019.
  * [11] M. Schwager, P. Dames, D. Rus, and V. Kumar.  A Multi-robot Control Policy for Information Gathering in the Presence of Unknown Hazards, pages 455–472.  Springer International Publishing, Cham, 2017.
  * [12] T. Tsiligirides.  Heuristic methods applied to orienteering.  Journal of the Operational Research Society, 35:797–809, 1984.
  * [13] O. Vaněk, M. Jakob, O. Hrstka, and M. Pěchouček.  Agent-based model of maritime traffic in piracy-affected waters.  Transportation Research Part C: Emerging Technologies, 36:157–176, 2013.