1  A Dynamic Boundary Guarding Problem with Translating Targets  Stephen L. Smith   Shaunak D. Bopardikar   Francesco Bullo  Abstract — We introduce a problem in which a service vehicle seeks to guard a deadline (boundary) from dynamically arriving mobile targets. The environment is a rectangle and the deadline is one of its edges. Targets arrive continuously over time on the edge opposite the deadline, and move towards the deadline at   a   fixed   speed.   The   goal   for   the   vehicle   is   to   maximize the fraction of targets that are captured before reaching the deadline. We consider two cases; when the service vehicle is faster than the targets, and; when the service vehicle is slower than the targets. In the first case we develop a novel vehicle policy based on computing longest paths in a directed acyclic graph. We give a lower bound on the capture fraction of the policy and show that the policy is optimal when the distance between the target arrival edge and deadline becomes very large. We present numerical results which suggest near optimal performance away from this limiting regime. In the second case, when the targets are slower than the vehicle, we propose a policy based on servicing fractions of the translational minimum Hamiltonian path. In the limit of low target speed and high arrival rate, the capture fraction of this policy is within a small constant factor of the optimal.  I. I NTRODUCTION  Vehicle motion planning in dynamic environments arises in many important autonomous vehicle applications. In areas such as environmental monitoring, surveillance and perimeter defence, the vehicle must re-plan its motion as it acquires in- formation on its surroundings. In addition, remote operators may add tasks to, or remove tasks from, the vehicle’s mission in real-time. In this paper we consider a problem in which a vehicle must defend a boundary in a dynamic environment with approaching targets. Static vehicle routing problems consider planning a path through a fixed number of locations. Examples include the traveling salesperson problem (TSP) [1], the deadline-TSP and vehicle routing with time-windows [2]. Recently, re- searchers have looked at the TSP with moving objects. In [3] the authors consider objects moving on straight lines and focus on the case when the objects are slower than the vehicle and when the vehicle moves parallel to the   x - or   y -axis. The same problem is studied in [4], but with arbitrary vehicle motion, and it is called the translational TSP. The authors of [4] propose a polynomial-time approximation scheme to catch all objects in minimum time. Other variations of the problem are studied in [5] and [6]. Dynamic vehicle routing (DVR) is a class of problems in which vehicles must plan paths through service demand  This material is based upon work supported in part by ARO-MURI Award W911NF-05-1-0219 and ONR Award N00014-07-1-0721. S. L. Smith, S. D. Bopardikar, and F. Bullo are all with the Cen- ter   for   Control,   Dynamical   Systems   and   Computation,   University   of California   at   Santa   Barbara,   Santa   Barbara,   CA   93106,   USA.   Email:  { stephen,shaunak,bullo } @engineering.ucsb.edu. L  W  Service vehicle  Deadline  Generator  v  Fig. 1.   The problem setup. Demands are shown as black disks approaching the deadline at speed   v . The service vehicle is a square.  locations that arrive sequentially over time. An early DVR problem was the dynamic traveling repairperson problem [7], [8], where each demand assumes a fixed location upon arrival, and the vehicle must spend some amount of on- site service time at each location. This problem has also been studied from the online algorithm perspective [9], [10]. Other recent DVR problems include DVR with demands that disappear if left unserviced for a certain amount of time [11], and demands with different priority levels [12]. In our earlier work [13], we introduced a DVR problem in which demands arrive on a line segment and move in a perpendicular direction at a fixed speed slower than the vehicle. We derived conditions on the demand arrival rate and demand speed for the existence of a vehicle routing policy which can serve all demands, and a proposed a policy based on the translational minimum Hamiltonian path.  Contributions:   In this paper we introduce the following problem (see Fig. 1): Targets (or demands) arrive according to a stochastic process on a line segment of length   W   . Upon arrival the demands move with fixed speed   v   towards a deadline which is at a distance   L   from the generator. A unit speed service vehicle seeks to capture the demands before they reach the deadline (i.e., within   L/v   time units of being generated). The performance metric is the fraction of demands that are captured before reaching the deadline. We assume that the arrival process is uniform along the line segment and temporally Poisson with rate   λ . In the case when the demands are faster than the service vehicle (i.e.,   v   ≥   1 ) we introduce the novel Longest Path policy, which is based on computing longest paths in a directed acyclic   reachability graph . When   L   ≥   vW   , we derive a lower bound on the capture fraction as a function of the system parameters. We show that the Longest Path policy is  arXiv:0908.3929v1 [cs.RO] 27 Aug 2009
2  the optimal policy when   L   is much greater than   vW   . In the case when the demands are slower than the service vehicle (i.e,   v <   1 ), we propose a policy based on the translational minimum Hamiltonian path called the TMHP-fraction policy. In the limit of low demand speed and high arrival rate, the capture fraction of this policy is within a small constant factor of the optimal. We present numerical simulations which verify our results, and show that the Longest Path policy performs very near the optimal even when   L < vW   . The   paper   is   organized   as   follows.   In   Section   II   we formulate the problem and in Section III we review some background material. In Section IV we consider the case of  v   ≥   1   and introduce the Longest Path Policy. In Section V we study   v <   1   and introduce the TMHP-fraction policy. Finally, in Section VI we present simulations results. II. P ROBLEM   F ORMULATION  Consider an environment   E   := [0 , W   ]   ×   [0 , L ]   ⊂   R 2   as shown in Figure 1. The line segment   [0 , W   ]   × { 0 } ⊂ E   is termed the   generator , and the segment   [0 , W   ]   × { L } ⊂ E  is termed the   deadline . The environment contains a single vehicle with position   p ( t ) = [ X ( t ) , Y   ( t )] T   ∈ E , modeled as a first-order integrator with unit speed. Demands (or targets) arrive in the environment according to a temporal Poisson process with rate   λ >   0 . Upon arrival, each demand assumes a uniformly distributed location on the generator, and then moves with constant speed   v >   0   in the positive   y -direction towards the deadline. If the vehicle intercepts a demand before the demand reaches the deadline, then the demand is captured. On the other hand, if the demand reaches the deadline before being intercepted by the vehicle, then the demand escapes. Thus, to capture a demand, it must be intercepted within   L/v   time units of being generated. We let   Q ( t )   ⊂ E   denote the set of all outstanding demand locations at time   t . If the   i th demand to arrive is captured, then it is removed from   Q   and placed in the set   Q capt   with cardinality   n capt . If the   i th demand escapes, then it is removed from   Q   and placed in   Q esc   with cardinality   n esc .  Causal Policy:   A causal feedback control policy for the vehicle is a map   P   :   E ×   F ( E )   →   R 2 , where   F ( E )   is the set of finite subsets of   E , assigning a commanded velocity to the service vehicle as a function of the current state of the system:    ̇ p ( t ) =   P ( p ( t ) ,   Q ( t )) .  Non-causal Policy:   In a non-causal feedback control policy the commanded velocity of the service vehicle is a function of the current and future state of the system. Such policies are not physically realizable, but they will prove useful in the upcoming analysis. Formally, let the generation of demands commence at time  t   = 0 , and consider the sequence of demands   ( q 1 , q 2 , . . . )  arriving at increasing times   ( t 1 , t 2 , . . . ) , with   x -coordinates  ( x 1 , x 2 , . . . ) .   We   can   also   model   the   arrival   process   by assuming that at time   t   = 0 , all demands are located in  [0 , W   ]   ×   ( −∞ ,   0] , move in the   y -direction at speed   v   for all   t >   0 , and are revealed to the service vehicle when they cross the generator. Thus, at time   t   = 0 , the position of the  i th demand is   ( x i , v ( t   −   t i )) . We can define a set containing the position of all demands in the region   [0 , W   ]   ×   ( −∞ ,   0]  at time   t   as   Q unarrived ( t ) . Then, a non-causal policy is one for which    ̇ p ( t ) =   P ( p ( t ) ,   Q ( t )   ∪ Q unarrived ( t )) .  Problem Statement:   The goal in this paper is to find causal policies   P   that maximize the fraction of demands that are captured   F cap ( P   ) , termed the   capture fraction , where  F cap ( P   ) := lim sup  t → + ∞  E  [   n capt   ( t )  n capt   ( t )+ n esc   ( t )  ]  .  III. P RELIMINARY   C OMBINATORIAL   R ESULTS  We now review the longest path problem, the distribution of demands in an unserviced region, and optimal tours/paths through a set of points.  A. Longest Paths in Directed Acyclic Graphs  A directed graph   G   = ( V, E )   consists of a set of vertices  V   and a set of directed edges   E   ⊂   V   ×   V   . An edge   ( v, w )   ∈  E   is directed from vertex   v   to vertex   w . A   path   in   G   is a sequence of vertices such that from each vertex in the sequence, there is an edge in   E   directed to the next vertex in the sequence. A path is   simple   if it contains no repeated vertices. A   cycle   is a path in which the first and last vertex in the sequence are the same. A graph   G   is   acyclic   if it contains no cycles. The longest path problem is to find a simple path of maximum length (i.e., a path that visits a maximum number of vertices). In general this problem is NP- hard as its solution would imply a solution to the well known Hamiltonian path problem [14]. However, if the graph is a DAG, then the longest path problem has an efficient dynamic programming solution [1] with complexity   O ( | V   | + | E | ) , that relies on topologically sorting [15] the vertices.  B. Distribution of Demands in an Unserviced Region  Demands arrive uniformly on the generator, according to a Poisson process with rate   λ . The following lemma describes the distribution of demands in an unserviced region. For a finite set   Q , we let   |Q|   denote its cardinality.  Lemma III.1 (Distribution of outstanding demands, [13])  Suppose the generation of demands commences at time   0  and no demands are serviced in the interval   [0 , t ] . Let   Q  denote the set of all demands in   [0 , W   ]   ×   [0 , vt ]   at time  t . Then, given a measurable compact region   R   of area   A  contained in   [0 , W   ]   ×   [0 , vt ] ,  P [ |R ∩ Q|   =   n ] = e −  ̄ λA ( ̄ λA ) n  n !   ,   where    ̄ λ   :=   λ/ ( vW   ) .  The previous lemma tells us that number of demands   N  in an serviced region of area   A   is a Poisson distributed with parameter   λA/ ( vW   ) . In addition, conditioned on   N   , the demands are independently and uniformly distributed.
3  C. The Euclidean Shortest Path/Tour Problems  Given a set   Q   of   n   points in   R 2 , the Euclidean traveling salesperson problem (ETSP) is to find the minimum-length tour (i.e., cycle) of   Q . Letting ETSP ( Q )   denote the minimum length of a tour of   Q , we can state the following result.  Theorem III.2 (Length of ETSP tour, [16])   Consider   a set   Q   of   n   points independently and uniformly distributed in a compact set   E   of area   |E| . Then, there exists a constant  β TSP   such that, with probability one,  lim  n → + ∞  ETSP ( Q )  √ n   =   β TSP  √ |E| .   (1) The constant   β TSP   has been estimated numerically as  β TSP   ≈   0 . 7120   ±   0 . 0002 , [17]. The Euclidean Minimum Hamiltonian Path (EMHP) prob- lem is to compute the shortest path through a set of points. In this paper we consider a constrained EMHP problem: Given a start point   s , a set of   n   points   Q , and a finish point   f   , all in   R 2 , determine the shortest path which starts at   s , visits each point in   Q   exactly once, and terminates at   f   . We let EMHP ( s ,   Q ,   f   )   denote the length of the shortest path.  Corollary III.3 (Length of EMHP)   Consider a set   Q   of   n  points independently and uniformly distributed in a compact set   E   of area   |E| , and any two points   s ,   f   ∈ E . Then with probability one,  lim  n → + ∞  EMHP ( s ,   Q ,   f   )  √ n   =   β TSP  √ |E| ,  where   β TSP   is defined in Theorem III.2.  The above corollary states that the length of the EMHP and the ETSP tour are asymptotically equal, and it follows directly from the fact that as   n   →   + ∞ , the diameter of   E   is negligible when compared to the length of the tour/path.  D. Translational Minimum Hamiltonian Path (TMHP)  The TMHP problem is posed as follows. Given initial coordinates;   s   of a start point,   Q   :=   { q 1 , . . . ,   q n }   of a set of points, and   f   of a finish point, all moving with speed   v   ∈ ]0 ,   1[  in the positive   y -direction, determine a minimum length path that starts at time zero from point   s , visits all points in the set   Q   and ends at the finish point. The following gives a solution [4] for the TMHP problem. (i) Define the map   g :   R 2   →   R 2   by  g( x, y ) =  (   x  √ 1   −   v 2   ,   y  1   −   v 2  )  .  (ii) Compute the EMHP that starts at   g v   ( s ) , passes through  { g( q 1 ) , . . . ,   g( q n ) }   =: g( Q )   and ends at   g( f   ) . (iii) To reach a translating point with initial position   ( x, y )  from the initial position   ( X, Y   ) , move towards the point  ( x, y   +   vT   ) , where  T   =  √ (1   −   v 2 )( X   −   x ) 2   + ( Y   −   y ) 2  1   −   v 2   −   v ( Y   −   y ) 1   −   v 2   .  The length TMHP v   ( s ,   Q ,   f   )   of the path is as follows.  Lemma III.4 (TMHP length, [4])   Let   the   initial   coordi- nates   s   = ( x s , y s )   and   f   = ( x f   , y f   ) , and the speed of the points   v   ∈   ]0 ,   1[ . Then,  TMHP v   ( s ,   Q ,   f   ) =   EMHP (g( s ) ,   g( Q ) ,   g( f   )) +   v ( y f   −   y s ) 1   −   v 2   .  IV. D EMAND   S PEED   G REATER   T HAN   V EHICLE   S PEED  Here we develop a policy for the case when the demand speed   v   ≥   1 . In this policy, the service vehicle remains on the deadline and services demands as per the longest path in a directed acyclic reachability graph. In this section we begin by introducing the reachability graph, and then proceed to state and analyze the Longest Path policy.  A. Reachable Demands  Consider a demand generated at time   t 1   ≥   0   at position  ( x,   0) . The demand moves in the positive   y -direction at speed  v   ≥   1 , and thus   ( x ( t ) , y ( t )) = ( x, v ( t   −   t 1 ))   for each   t   ∈  [ t 1 , T   ] , where   T   is either the time of escape (i.e.,   T   =   L/v   +  t 1 ), or it is the time of capture. Now, given the service vehicle location   ( X ( t ) , Y   ( t )) , a demand with position   ( x, y ( t ))   is reachable if and only if  v | X ( t )   −   x | ≤   Y   ( t )   −   y ( t ) .   (2) That is, the service vehicle must be at a height of at least  v | X ( t )   −   x |   above the demand in order to capture it.  Definition IV.1 (Reachable set)   The reachable set from a position   ( X, Y   )   ∈ E   is  R ( X, Y   ) :=   { ( x, y )   ∈ E   :   v | X   −   x | ≤ | Y   −   y |} .  If the service vehicle is located at   ( X, Y   ) , then a demand can be captured if and only if it lies in the set   R ( X, Y   ) .  An example of the reachable set is shown in Figure 2. Next, given a demand in the reachable set, the following motion gives a method of capture.  Definition IV.2 (Intercept motion)   Consider a vehicle po- sition   (( X ( ̄ t ) , Y   ( ̄ t ))   and a demand position   ( x, y ( ̄ t ))   ∈  R ( X ( ̄ t ) , Y   ( ̄ t ))   at time    ̄ t   ≥   0 . In intercept motion, the service vehicle captures the demand by first moving horizontally at unit speed to the position   ( x i , Y   ( ̄ t )) , and then waiting at the location for the demands arrival.  Lemma IV.3 (Optimality of intercept motion)   Consider  v   ≥   1 , and let the service vehicle be initially positioned on the deadline. Then, there is an optimal policy in which the service vehicle uses only intercept motion. Proof:   Let the service vehicle be positioned at   ( X, L ) , and consider a demand at   ( x, y )   ∈   R ( X, L ) . From equa- tion (2), we have   v | X   −   x | ≤   L   −   y . If   v | X   −   x |   =   L   −   y , then deadline motion is the only way in which the demand can be captured. Thus, assume that   v | X   −   x |   < L   −   y , and consider two cases; Case 1 in which intercept motion is used, and Case 2 in which the demand is captured at a location  ( x, Y   ) , where   Y < L .
4 Reachable demands  Fig. 2.   The construction of the reachability graph. The top-left figure shows the set of reachable points from a vehicle positioned on the deadline. The top-right and bottom-left figures show the reachable set from demand locations. The bottom-right figure shows the reachability graph.  Notice   that   the   position   of   each   outstanding   demand relative to the service vehicle position at capture is the same in Case 1 as in Case 2. Thus, the reachable set in Case 2 is a strict subset of reachable set in Case 1 and the vehicle gains no advantage by moving off of the deadline. Next, consider the set of demands in   R ( X ( ̄ t ) , Y   ( ̄ t )) , and suppose   the   vehicle   chooses   to   capture   demand   i ,   with position   q i ( ̄ t ) = ( x i , y i ( ̄ t ))   ∈   R ( X ( ̄ t ) , Y   ( ̄ t )) . Upon capture at time   T   , the service vehicle can recompute the reachable set, and select a demand that lies within. Since all demands translate together, every demand that was reachable from  q i ( ̄ t ) , is reachable from   q i ( T   ) . Thus, the service vehicle can “look ahead” and compute the demands that will be reachable from each captured demand position. This idea motivates the concept of a reachability graph.  Definition IV.4 (Reachability graph)   For   v   ≥   1 ,   the reachability graph of a set of points   { q 1 , . . . ,   q n } ∈ E , is a directed acyclic graph with vertex set   V   :=   { 1 , . . . , n } , and edge set   E , where for   i, j   ∈   V   , the edge   ( i, j )   is in   E   if and only if   q j   ∈   R ( q i )   and   j   6   =   i .  Given a set   Q   of   n   outstanding demands, and a vehicle position   ( X, Y   ) , we can compute the corresponding reach- ability graph (see Fig. 2) in   O ( n 2 )   computation time. In addition, by Section III-A we can compute the longest path in a reachability graph in   O ( n 2 )   computation time.  B. A Non-causal Policy and Upper Bound  To derive an upper bound for   v   ≥   1 , we begin by considering a non-causal policy. In the online algorithms Deadline  Generator  non-causal path  causal path  Fig. 3.   A snapshot in the evolution of the Non-causal Longest Path policy. The vehicle has planned the solid red path through all demands, including those that have not yet arrived. In comparison, a dashed causal longest path is shown, which only considers demands that have arrived.  literature, such a policy would be referred to as an   offline algorithm   [9]. Figure 3 shows an example of a path generated by the Non-causal Longest Path policy. Note that the service vehicle will intercept each demand on the deadline, and thus the path depicts which demands will be captured, and in what order.  Non-causal Longest Path (NCLP) policy Assumes : Vehicle is located on deadline and   v   ≥   1 . Compute the reachability graph of the vehicle position 1  and all demands in   Q (0)   ∪ Q unarrived (0) . Compute a longest path in this graph, starting at the 2  service vehicle location. Capture demands in the order they appear on the path, 3  intercepting each demand on the deadline.  Lemma IV.5 (Optimal non-causal policy)   If   v   ≥   1 , then the Non-causal Longest Path policy is an optimal non-causal policy. Moreover, if   v   ≥   1 , then for every causal policy   P   ,  F cap ( P   )   ≤   F cap (NCLP) .  Proof:   The reachability graph   Q (0)   ∪ Q unarrived (0)  contains every possible path that the service vehicle can follow. When   v   ≥   1   the graph is a directed acyclic graph and thus the longest path (i.e., the path which visits the most vertices in the graph) is well defined. The vehicle uses intercept motion, and thus by Lemma IV.3 the NCLP policy is an optimal non-causal policy, and its capture fraction upper bounds every causal policy.  C. The Longest Path Policy  We now introduce the Longest Path policy. In the LP policy, the fraction   η   is a design parameter. The lower   η  is chosen, the better the performance of the policy, but this
5 p a   ( t   1   )   p b   ( t   1   )  scenario (a)  scenario (b)  q 1  q 2  q 3  q 4  Fig. 4.   Scenario (a) and (b) for the proof of Theorem IV.6. Path (a) visits five demands and thus   L a   = 5 . Path (b) visits four demands, yielding  m   = 4 . The demand   q 2   is the highest on path (b) that can be captured from   p a ( t 1 ) . Thus,   n   = 1 , and   5 =   L a   > m   −   n   = 3 .  comes at the expense of increased computation.  The Longest Path (LP) policy Assumes : Vehicle is located on deadline and   v   ≥   1  Compute the reachability graph of the vehicle position 1  and all demands in   Q (0) . Compute a longest path in this graph, starting at the 2  service vehicle location. Capture demands in the order they appear on the path, 3  intercepting each demand on the deadline. Once a fraction   η   ∈   ]0 ,   1]   of the demands on the path 4  have been serviced, recompute the reachability graph of all outstanding demands and return to step 2. In the following theorem, we relate the Longest Path policy to its non-causal relative. Such a bound is referred to as a   competitive ratio   in the online algorithms literature [9].  Theorem IV.6 (Optimality of Longest Path policy)   If  v   ≥   1 , then  F cap (LP)   ≥  (  1   −   vW L  )  F cap (NCLP) ,  and thus the LP policy is optimal as   vW/L   →   + ∞ . Proof:   Suppose that the generation of demands begins at   t   = 0   and let us consider two scenarios; (a) the vehicle uses the Longest Path policy, and (b) the vehicle uses the Non-causal Longest Path policy. Then, at any instant in time  t 1   >   0   we can compare the number of demands captured in scenario (a) to the number captured in scenario (b) (refer to Fig. 4). Let us consider a time instant   t 1   where in scenario (a), the vehicle is recomputing the longest path through all outstand- ing demands   Q ( t 1 ) . Let us denote by   p a ( t 1 )   and   p b ( t 1 ) , the vehicle position in scenario (a) and scenario (b), respectively, at time   t 1 . In scenario (b), let the path that the vehicle will take through   Q ( t 1 )   be given by   ( q 1 ,   q 2 , . . . ,   q m )   ∈ Q ( t 1 ) . The demand   q 1   is reachable from   p b ( t 1 ) , but it may not be reachable from   p a ( t 1 ) . However, a lower bound on the length of the longest path in scenario (a) is:   ( q n +1 ,   q n +2 , . . . ,   q m ) , where   q n +1 ,   n   ∈ { 0 , . . . , m   −   1 } , is the highest demand that can be captured from   p a ( t 1 ) , see Fig. 4. Thus, the length of the longest path in scenario (a),   L a , is at least  L a   ≥   m   −   n,   (3) where   m   is the length of the path in scenario (b). Now, since the deadline has width   W   , the vehicle in scenario (a) can capture any demand   ( x, y )   with   y   ≤   L − vW   . Thus, the demands   q 1 , . . . ,   q n   must all have   y -coordinates in  ] L   −   vW, L ] . Let the total number of outstanding demands at time   t 1   be   N tot . Then, conditioned on   N tot , by Lemma III.1, the expected number of outstanding demands contained in  [0 , W   ]   ×   ] L   −   vW, L ]   is   N tot vW/L . Hence,  E   [ n | N tot ] =   N tot  vW L   F cap (NCLP) .   (4) Similarly, for the length of the path through   Q ( t 1 )   in scenario (b), we have  E   [ m | N tot ] =   N tot F cap (NCLP) .   (5) Combining equations (4) and (5) with equation (3) we obtain  E   [ L a | N tot ]   ≥   N tot  (  1   −   vW L  )  F cap (NCLP) ,  E  [   L a  N tot   | N tot  ]  ≥  (  1   −   vW L  )  F cap (NCLP) .  But   L a /N tot   is the fraction of outstanding demands in   Q ( t 1 )  that will be captured in scenario (a), and it does not depend on the value of   N tot . By the law of total expectation  E  [   L a  N tot  ]  =   E  [  E  [   L a  N tot   | N tot  ]]  ≥  (  1   −   vW L  )  F cap (NCLP) .  Each   time   the   longest   path   is   recomputed,   the   path   in scenario (a) will capture at least this fraction of demands. Thus, we have   F cap (LP)   ≥   E   [ L a /N tot ]   and have proved the result.  Remark IV.7 (Conservativeness of bound)   The bound in Theorem   IV.6   is   conservative.   This   is   primarily   due   to bounding the expected distance between the causal and non- causal paths by   W   . The distance between two independently and uniformly distributed points in   [0 , W   ] , is   W/ 3 . The distance is even less if the points are positively correlated (as is likely the case for the distance between paths). Thus, it seems that it may be possible to increase the bound to  F cap (LP)   ≥  (  1   −   vd L  )  F cap (NCLP) ,  where   d < W/ 3 .     The previous theorem establishes the performance of the Longest Path policy relative to a non-causal policy. However, the LP policy is difficult analyze directly. This is due to the fact that the position of the vehicle at time   t   depends on the positions of all outstanding demands in   Q ( t ) . Thus, our
6  approach is to lower bound the capture fraction of the LP policy with a greedy policy:  The Greedy Path (GP) policy Assumes : Vehicle is located at   ( X, L )  Compute the reachability set   R ( X, L ) . 1  Capture the demand in   R ( X, L )   with the highest 2  y -coordinate using intercept motion. Repeat. 3  Given a set of outstanding demands   Q ( t )   at time   t , the Greedy Path policy generates a suboptimal longest path through   Q ( t ) . In addition, the vehicle position is independent of all outstanding demands, except the demand currently being captured. Thus, the capture fraction of the Greedy Path policy provides a lower bound for the capture fraction of the Longest Path policy. We are now able to establish the following result.  Theorem IV.8 (Lower Bound for Longest Path policy)  If   L   ≥   vW   , then for the Longest Path policy  F cap (LP)   ≥   F cap (GP)   ≥   1  √ πα   erf( √ α ) + e − α   ,  where   α   =   λW/ 2   and   erf   :   R   →   [ − 1 ,   1]   is the error function. Proof:   We begin by looking at the expression for the capture fraction. Notice that if   n capt ( t )   >   0   for some   t >   0 , then  lim sup  t → + ∞  E  [   n capt   ( t )  n capt   ( t )+ n esc ( t )  ]  = lim sup  t → + ∞  E  [  1 1+   n esc ( t )  n capt   ( t )  ]  ≥  (  1 + lim sup  t → + ∞  E  [   n esc ( t )  n capt   ( t )  ]) − 1  ,  (6) where the last step comes from an application of Jensen’s inequality [18]. Thus, we can determine a lower bound on the capture fraction by studying the number of demands that escape per captured demand. Let us study the time instant   t   at which the service vehicle captures its   i th demand, and determine an upper bound on the number of demands that escape before the service vehicle captures its   ( i   + 1) th demand. Since we seek a lower bound on the capture fraction of the LP policy, we may consider the path generated by the Greedy Path policy. In addition, we consider the worst-case service vehicle position; namely, the position   (0 , L )   (or equivalently   ( W, L ) ). From the position   (0 , L ) , the reachable set is  R (0 , L ) =   { ( x, y )   ∈ E   :   vx   ≤   L } .  Let   R y   denote the reachable set intersected with   [0 , W   ]   ×  [ L   −   y, L ] , where   y   ∈   [0 , L ] , and let   | R y   |   denote its area. Then,  | R y   |   =  {   y 2  2 v   ,   if   y   ≤   vW , yW   −   vW   2  2   ,   if   y > vW .  An illustration of the set   R y   is shown in Figure 5. Let   y d Deadline  Generator  R   y   d  y   d   esc   y   d  W  L  Fig. 5.   The setup for the proof of Theorem IV.8. The service vehicle is located at   (0 , L ) . All demands in the region esc y d   escape while capturing the demand with the highest   y -coordinate.  be the   y -distance to the reachable demand with the highest  y -coordinate. That is,  y d   =   min  ( x,y ) ∈Q ( t ) ∩ R (0 ,L ) { L   −   y } ,  where   Q ( t )   is the set of outstanding demands at time   t . By Lemma III.1, the probability that a subset   B ⊂ E   with area  |B|   contains zero demands is given by  P [ |B ∩ Q ( t ) |   = 0] = e − λ |B| / ( vW   ) ,  where   |B ∩ Q ( t ) |   denotes the cardinality of the finite set  B ∩ Q ( t ) . Thus,  P [ y d   > y ] =   P [ | R y   ∩ Q ( t ) |   = 0] = e − λ | R y   | / ( vW   ) .  The probability density function of   y d   for   y d   ≤   vW   is  f   ( y ) =   d dy   (1   −   P [ y d   > y ]) =   d dy   e − λy 2 / (2 v 2 W   )  =   λ v 2 W y e − λy 2   / (2 v 2   W   ) .  Now, given   y d , all demands residing in the region esc y d   := ([0 , W   ]   ×   [ L   −   y d , L ])   \   R y d   will escape (see Fig. 5). The area of esc y d   is  | esc y d   |   =  {  y d W   −   y 2  d  2 v   ,   if   y d   ≤   vW ,  vW   2  2   ,   if   y d   ≥   vW .  From Section III-B, the expected number of outstanding demands in an unserviced region of area   A   is   λA/ ( vW   ) . Thus, given that the vehicle is located at   (0 , L ) , the expected number of demands that escape while the service vehicle is capturing its   ( i   + 1) th demand is given by  E   [ n esc ,i ] =   λ vW   E   [ | esc y d   | ] =   λ vW  [∫   vW  0  (  yW   −   y 2  2 v  )  f   ( y ) dy   +   vW   2  2   P [ y d   > vW   ]  ]  .  Applying the probability density function and cumulative distribution function of   y d   we obtain  E   [ n esc ,i ] =   λ 2  v 3 W   2  ∫   vW  0  (  yW   −   y 2  2 v  )  y e − λy 2 / (2 v 2 W   ) dy  +   λW  2   e − λW/ 2 .   (7)
7  To evaluate the integral, consider the change of coordinates  z   :=   y/vW   , and define   α   :=   λW/ 2 . After simplifying, the integral becomes  4 α 2  ∫   1 0  (  z 2   −   z 3  2  )  e − αz 2  dz.  Integrating by parts we obtain  √ πα   erf( √ α ) +   α e − α   + e − α   −   1 ,   (8) where   erf :   R   →   [ − 1 ,   1]   is the error function:  erf( x ) = 2  π  ∫   x  0  e − t 2  dt.  Substituting equation (8) into equation (7) we obtain  E   [ n esc ,i ] =   √ πα   erf( √ α ) + e − α   −   1 .  Since   E   [ n esc ,i ]   is computed for the worst-case vehicle posi- tion   (0 , L ) , and since this expression holds at every capture, we have that  lim sup  t → + ∞  E  [   n esc   ( t )  n capt   ( t )  ]  ≤ √ πα   erf( √ α ) + e − α   −   1 ,  and thus by equation (6) we obtain the desired result. V. D EMAND SPEED LESS THAN VEHICLE SPEED  In this section we study the case when the demand speed  v <   1 . For this case, an upper bound on the capture fraction has been derived in [13]. We introduce a policy which is a variant of the TMHP-based policy in [13], and lower bound its capture fraction in the limit of low demand speed and high demand arrival rate.  A. Capture Fraction Upper Bound  The following theorem upper bounds the capture fraction of every policy for the case of   v <   1 .  Theorem V.1 (Capture fraction upper bound, [13])   If  v <   1 , then for every causal policy   P  F cap ( P   )   ≤   min  {  1 ,   2  √ vλW  }  .  The proof of the above theorem is contained in [13], and relies on a computation of the expected minimum distance between demands. Notice that for low demands speed, i.e.,  v      1 , it may be possible to achieve a capture fraction of one, even for high arrival rates.  B. The TMHP-fraction Policy  In Section III-D we reviewed the translational minimum Hamiltonian Path (TMHP) through a set of demands. The  Fig. 6.   The TMHP-fraction policy. The left-hand figure shows a TMHP through all outstanding demands. The right-figure shows the instant when the vehicle has followed the path for   L/ (2 v )   time units and recomputes its path, allowing some demands to escape.  following policy utilizes this path to service demands.  The TMHP-fraction (TF) policy Assumes : Vehicle is located on the line   y   =   L/ 2 . Compute a translational minimum Hamiltonian path 1  through all outstanding demands in   [0 , W   ]   ×   [0 , L/ 2] , starting at the service vehicle position, and terminating at the demand with the lowest   y -coordinate.  if   time to travel entire path is less than   L/ (2 v )   then 2  Service all outstanding demands by following the 3  computed path.  else 4  Service outstanding demands along the computed 5  path for   L/ (2 v )   time units. Repeat. 6  Figure 6 shows an example of the TMHP-fraction policy. In contrast with the LP policy, where the vehicle remains on the deadline, in the TMHP-fraction policy the vehicle follows the TMHP using minimum time motion between demands as described in Section III-D. Notice that none of the demands in the region   [0 , W   ]   ×   [0 , L/ 2]   at time   t   will have escaped before time   t   +   L/ (2 v ) . Thus, the vehicle is guaranteed that for the first   L/ (2 v )   time units, all demands on the TMHP path are still in the environment. For the TMHP-fraction policy we have the following result.  Theorem V.2 (TMHP-fraction policy lower bound)   In the limit as   v   →   0 +   and   λ   →   + ∞ , the capture fraction of the TMHP-fraction policy satisfies  F cap (TF)   ≥   min  {  1 ,   1  β TSP  √ vλW  }  .  Proof:   Consider the beginning of an iteration of the policy, and assume that the duration of the previous iteration was   L/ (2 v ) . In this case, the vehicle has   y -coordinate   Y   ∈  [ L/ 2 , L ] , and by Lemma III.1, the region   R   := [0 , W   ]   ×  [0 , L/ 2]   contains a number of demands   N   that is Poisson distributed with parameter   λL/ (2 v ) . Conditioned on   N   , the demands are independently and uniformly distributed in   R . Now, we make use of the following three facts. First, as  v   →   0 + , the length of the TMHP constrained to start at the vehicle location and end at the lowest demand, is equal to
8  the length of the EMHP in the corresponding static instance, as described in Lemma III.4. Second, from Corollary III.3, for uniformly distributed points, the asymptotic length of a constrained EMHP is equal to the asymptotic length of the ETSP tour. Third, as   v   →   0 + , and   λ   →   + ∞ , we have that   N   tends to   + ∞   with probability one. Using the above facts we obtain that the length of the TMHP starting at the vehicle position, passing through all demands in   R , and terminating at the demand with the lowest   y -coordinate, has length   β TSP  √ N W L/ 2   in the limiting regime as   v   →   0 + , and   λ   →   + ∞ . The vehicle will follow the TMHP for at most   L/ (2 v )  time units, and thus will service   cN   demands, where  c   = min  {  1 ,  √ L β TSP v √ 2 N W  }  .  Now, the random variable   N   has expected value   E   [ N   ] =  λL/ (2 v )   and variance   σ 2  N   =   λL/ (2 v ) . By the Chebyshev inequality,   P [ | N   −   E   [ N   ] | ≥   α ]   ≤   σ 2  N   /α 2 , and thus letting  α   =   √ v E   [ N   ] , we have  P [ N   ≥   (1 +   √ v ) E   [ N   ]]   ≤   1  v E   [ N   ] =   2  λL .  Thus, we have  c   ≥   min  {  1 ,   1  β TSP  √ (1 +   √ v ) vλW  }  .  with probability at least   1 − 2 / ( λL ) . In the limit as   λ   →   + ∞ , with probability 1,  c   ≥   min  {  1 ,   1  β TSP  √ vλW  }  .   (9) Therefore, if the previous iteration had duration at least  L/ (2 v ) , then the total fraction of demands captured in the current iteration is given by equation (9). The other case is that the previous iteration had duration  T < L/ (2 v ) . In this case, all outstanding demands in the region   R   := [0 , W   ] × [0 , L/ 2]   lie in a subset   [0 , W   ] × [0 , vT   ] , and the subset contains a number of demands   N   that is Poisson distributed with parameter   λT   ≤   λL/ (2 v ) . Thus, in this case there are fewer outstanding demands, and the bound on   c   still holds. Thus,   F cap (TF)   ≥   c , and we obtain the desired result.  Remark V.3 (Bound comparison)   In the limit as   v   →   0 + , and   λ   →   + ∞ , the capture fraction of the TMHP-fraction policy is within a factor of   2 β TSP   ≈   1 . 42   of the optimal.     VI. S IMULATIONS  We now present two sets of results from numerical ex- periments. The first set compares the Longest Path policy with   η   = 1   to the Non-causal Longest Path policy and to the theoretical lower bound in Theorem IV.8. The second set compares the TMHP-fraction policy to the policy indepen- dent upper bound in Theorem V.1 and the lower bound in Theorem V.2. 0   0.02   0.04   0.06   0.08   0.1  0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9  1  Arrival rate Capture fraction LP policy experimental  Noncausal LP experimental  Lower bound  (a)   v   = 2   and   L > vW   . 0   0.02   0.04   0.06   0.08   0.1  0  0.1  0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9  1  Arrival rate Capture fraction Longest Path  Fundamental limit   (b)   v   = 5   and   L < vW   . Fig. 7.   Simulation results for LP policy (solid red line with error bars showing   ±   one standard deviation) and the NCLP policy (dashed black line) for an environment of width   W   = 120   and length   L   = 500 . In (a),  L > vW   , and the lower bound in Theorem IV.8 is shown in solid green. 400   500   600   700   800 0.4 0.5 0.6 0.7 0.8 0.9 1  Arrival rate Capture fraction Experimental  Upper bound  Lower bound  (a) Demand speed   v   = 0 . 01 . 80   90   100   110   120 0.4 0.5 0.6 0.7 0.8 0.9 1  Arrival rate Capture fraction Experimental  Upper bound  Lower bound   (b) Demand speed   v   = 0 . 05 . Fig. 8.   Simulation results for TMHP-fraction policy. The solid black curve shows the upper bound in Theorem V.1 and the dashed line shows the lower bound in Theorem V.2. Numerical results are shown with error bars.  To simulate the LP and the NCLP policies, we perform   10  runs of the policy, where each run consists of   5000   demands. A comparison of the capture fractions for the two policies is presented in Figure 7. When   L > vW   , the capture fraction of the LP policy is nearly identical to that of the NCLP policy. Even in Figure 7(a), where   L < vW   , the capture fraction of the LP policy is within   2%   of the NCLP policy, and thus the optimal. This suggests that the Longest Path policy is essentially optimal over a large range of parameter values. To simulate the TMHP-fraction policy, the   linkern 1  solver is used to generate approximations to the optimal TMHP. For each value of arrival rate, we determine the capture fraction by taking the mean over   10   runs of the policy. A comparison of the simulation results with the theoretical results from Section V are presented in Figure 8. For   v   = 0 . 01   in Fig. 8(a), the experimental results are in near exact agreement with the theoretical lower bound in Theorem V.1. For   v   = 0 . 05   in Fig. 8(b), the experimental re- sults are within   5%   of the theoretical lower bound. However, notice that the experimental capture fraction is smaller than the theoretical lower bound. This is due to several factors. First, we have not reached the limit as   v   →   0 +   and   λ   →   + ∞  where the asymptotic value of   β TSP   ≈   0 . 712   holds. Second, we are using an approximate solution to the optimal TMHP,  1   linkern   is   freely   available   for   academic   research   use   at  http://www.tsp.gatech.edu/concorde.html .
9  generated via the linkern solver. VII. C ONCLUSIONS  In this paper we introduced a pursuit problem in which a vehicle must guard a deadline from approaching demands. We presented novel policies in the case when the demand speed is greater than the vehicle speed, and in the case when the demand speed is less than the vehicle speed. In the former case we introduced the Longest Path policy which is based on computing longest paths in the directed acyclic reachability graph, and in the latter case we introduced the TMHP- fraction policy. For each policy, we analyzed the fraction of demands that are captured. There are many areas for future work. The Longest Path policy has promising extensions to the case when demands have different priority levels, and to the case of multiple vehicles. We would also like to fully characterize the capture fraction when   L < vW   , and tighten our existing bounds to reflect the near optimal performance shown in simulation. R EFERENCES [1]   N. Christofides,   Graph Theory: An Algorithmic Approach .   Academic Press, 1975. [2]   N. Bansal, A. Blum, S. Chawla, and A. Meyerson, “Approximation algorithms for deadline-TSP and vehicle routing with time-windows,” in   ACM Symposium on the Theory of Computing , Chicago, IL, 2004, pp. 166 – 174. [3]   P. Chalasani and R. Motwani, “Approximating capacitated routing and delivery problems,”   SIAM Journal on Computing , vol. 28, no. 6, pp. 2133–2149, 1999. [4]   M. Hammar and B. J. Nilsson, “Approximation results for kinetic variants of TSP,”   Discrete and Computational Geometry , vol. 27, no. 4, pp. 635–651, 2002. [5]   C. S. Helvig, G. Robins, and A. Zelikovsky, “The moving-target traveling salesman problem,”   Journal of Algorithms , vol. 49, no. 1, pp. 153–174, 2003. [6]   Y. Asahiro, E. Miyano, and S. Shimoirisa, “Grasp and delivery for moving   objects on   broken   lines,”   Theory   of Computing   Systems , vol. 42, no. 3, pp. 289–305, 2008. [7]   H.   N.   Psaraftis,   “Dynamic   vehicle   routing   problems,”   in   Vehicle Routing: Methods and Studies , B. Golden and A. Assad, Eds.   Elsevier (North-Holland), 1988, pp. 223–248. [8]   D. J. Bertsimas and G. J. van Ryzin, “A stochastic and dynamic vehicle routing problem in the Euclidean plane,”   Operations Research , vol. 39, pp. 601–615, 1991. [9]   A. Borodin and R. El-Yaniv,   Online Computation and Competitive Analysis .   Cambridge University Press, 1998. [10]   S. O. Krumke, W. E. de Paepe, D. Poensgen, and L. Stougie, “News from the online traveling repairmain,”   Theoretical Computer Science , vol. 295, no. 1-3, pp. 279–294, 2003. [11]   M.   Pavone,   N.   Bisnik,   E.   Frazzoli,   and   V.   Isler,   “A   stochastic and   dynamic   vehicle   routing   problem   with   time   windows   and customer impatience,”   ACM/Springer Journal of Mobile Networks and   Applications ,   2008,   to   appear.   [Online].   Available:   http: //ares.lids.mit.edu/papers/Pavone.Bisnik.ea.MONE08.pdf [12]   S. L. Smith, M. Pavone, F. Bullo, and E. Frazzoli, “Dynamic vehicle routing with priority classes of stochastic demands,”   SIAM Journal on Control and Optimization , Feb. 2009, submitted. [13]   S. D. Bopardikar, S. L. Smith, F. Bullo, and J. P. Hespanha, “Dy- namic vehicle routing for translating demands: Stability analysis and receding-horizon policies,”   IEEE Transactions on Automatic Control , Mar. 2009, submitted. [14]   B. Korte and J. Vygen,   Combinatorial Optimization: Theory and Algorithms , 4th ed., ser. Algorithmics and Combinatorics.   Springer, 2007, vol. 21. [15]   T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,   Introduction to Algorithms , 2nd ed.   MIT Press, 2001. [16]   J. Beardwood, J. Halton, and J. Hammersly, “The shortest path through many points,” in   Proceedings of the Cambridge Philosophy Society , vol. 55, 1959, pp. 299–327. [17]   A. G. Percus and O. C. Martin, “Finite size and dimensional depen- dence of the Euclidean traveling salesman problem,”   Physical Review Letters , vol. 76, no. 8, pp. 1188–1191, 1996. [18]   L. Breiman,   Probability , ser. Classics in Applied Mathematics.   SIAM, 1992, vol. 7, corrected reprint of the 1968 original.