## 3 Warehouse Delivery Problem
### Formalization
#### 3.1.2 Solution Formulation  
Having defined the warehouse delivery problem in terms of a warehouse environment and the tasks to be performed within that warehouse, we now turn to formalizing the notion of a solution to this problem. After some supporting definitions and terminology,  
Figure 2: Item deliveries from \(l_{1}\) to \(s_{1}\) and from \(l_{2}\) to \(s_{2}\). Their corresponding replacement empty pallet deliveries are from \(p_{1}\) to \(l_{1}\) and \(l_{2}\), respectively. we introduce the notion of a _robot assignment_ that assigns tasks and walks to robots in the warehouse. Then, we define additional restrictions that make a robot assignment a solution to a warehouse problem instance. _Task sequences_. Ultimately our goal is to assign to a robot a set of tasks to be executed in a particular order. To this end, we define a _task sequence_ over a set \(T\) of tasks as a (possibly empty) sequence \(\langle t_{0},\ldots,t_{n}\rangle\) such that \(t_{i}\in T\) and \(t_{i}\
eq t_{j}\) for all \(i\
eq j\). We denote the set of all task sequences over \(T\) as \(\mathcal{T}_{T}\). Next, we clarify sequence operations and terminology. Firstly, a _subsequence_ is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements. We use the notation \(\vec{v}\sqsubseteq\vec{w}\) to denote that \(\vec{v}\) is a subsequence of \(\vec{w}\). Secondly, we sometimes treat sequences as sets and apply set operations to sequences by ignoring their order and only considering their elements. For example, \(\langle 1,2,1,4\rangle\cap\langle 3,4,1\rangle=\{1,4\}\). _Timed walks_. A _walk_ is a finite traversal along the vertices and edges of a graph, where vertices and edges may be visited multiple times. Since we consider graphs with at most one edge between any two vertices, we identify walks by their sequence of vertices. Given a warehouse with vertices \(V\), we define the notion of a _timed walk_ as a sequence of _route points_, \((v,a,e)\in V\times\mathbb{N}\times\mathbb{N}\), where \(v\in V\) is a vertex in the warehouse, \(a\) is the arrival time at \(v\), and \(e\) is the exit time from \(v\). To warrant the feasibility of a timed walk in a warehouse, the arrival and exit times at each vertex must be compatible with the edge weights in the warehouse. That is, given a warehouse \(W\) with vertices \(V\), edges \(E\), and edge weights \(f_{E}\), we require for each _timed walk_\(\langle(v_{0},a_{0},e_{0}),\ldots,(v_{n},a_{n},e_{n})\rangle\)_feasible in \(W\)_ that  
1. \((v_{i},v_{i+1})\in E\),
2. \(a_{i}\leq e_{i}\), and
3. \(e_{i}+f_{E}((v_{i},v_{i+1}))\leq a_{i+i}\). We use \(\mathcal{W}_{W}\) to denote the set of timed walks feasible in warehouse \(W\). **Robot Assignment**. Given a warehouse \(W=(V,E,f_{E},C,R,f_{H},f_{S})\) and a task execution graph \((T,D,f_{D},f_{V})\), we define a _robot assignment_ as a pair \((f_{T},f_{W})\) such that:  
1. \(f_{T}:R\rightarrow\mathcal{T}_{T}\) assigns to each robot a task sequence over \(T\); and
2. \(f_{W}:R\rightarrow\mathcal{W}_{W}\) assigns to each robot a timed walk feasible in \(W\). The robot assignment specifies two key pieces of information. Firstly, it specifies the assignment of robots to tasks, also called the robot's _task sequence assignment_, and secondly, it specifies the movements of each robot within the warehouse, referred to as the _walk assignment_. For instance,  
\[f_{T}(\tau_{1})=\langle t_{1},t_{2},t_{3},t_{4}\rangle\text{ and }f_{T}(\tau_{2})= \langle t_{5},t_{6},t_{7},t_{8}\rangle \tag{3}\]  
are task sequence assignments for robot \(r_{1}\) and \(r_{2}\) in our example (cf. Figure 2); it is further illustrated in Table 1. This task assignment makes each robot perform both an item delivery as well as an empty pallet replacement. However, other alternatives are also possible, such as where one robot performs both item deliveries and the other performs both pallet replacements. Corresponding time walks for both robots in our example warehouse (cf.