Traveling Salesman Problems Motivated by Robot NavigationA Robot Navigation ProblemMarkov Decision Process ModelExponential DiscountingSolving MDPSolving the wrong problemTackle an easier problemDiscounted-Reward TSPApproximation AlgorithmsRelated Problemsk-TSPMismatchOrienteering ProblemOur ResultsSlide 15Eliminating ExponentiationOptimum pathNew problem: Approximate Min-Excess PathUsing Min-Excess PathSolving Min-Excess Path problemSolving Min-Excess Path problemApproximating path lengthDecompose optimum pathDecomposition AnalysisDynamic program for Min-Excess PathSolving Orienteering Problem: special caseSolving Orienteering ProblemBudget Prize-Collecting Steiner Tree problemSummaryOpen QuestionsFuture directionsTraveling Salesman Problems Motivated by Robot NavigationMaria Minkof MITWith Avrim Blum, Shuchi Chawla, David Karger, Terran Lane, Adam MeyersonA Robot Navigation Problem•Robot delivering packages in a building•Goal to deliver as quickly as possible•Classic model: Traveling Salesman Problem•Find a tour of minimum length•Additional constraints:•some packages have higher priority•uncertainty in robot’s behavior •battery failure•sensor error, motor control errorMarkov Decision Process Model•State space S•Choice of actions aA at each state s•Transition function T(s’|s,a)•action determines probability distribution on next state•sequence of actions produces a random path through graph•Rewards R(s) on states•If arrive in state s at time t, receive discounted reward tR(s) for     •MDP Goal: policy for picking an action from any state that maximizes total discounted rewardExponential Discounting•Motivates to get to desired state quickly•Inflation: reward collected in distant future decreases in value due to uncertainty • at time t robot loses power with fixed probability•probability of being alive at t is exponentially distributed•discounting reflects value of reward in expectationSolving MDP•Fixing action at each state produces a Markov Chain with transition probabilities pvw•Can compute expected discounted reward v if start at state v:v = rv + w pvw t(v,w) w•Choosing actions to optimize this recurrence is polynomial time solvable •Linear programming•Dynamic programming (like shortest paths)Solving the wrong problem•Package can only be delivered once•So should not get reward each time reach target•One solution: expand state space•New state = current location  past locations (packages already delivered)•Reward nonzero only on states where current location not included in list of previously visited•Now apply MDP algorithm•Problem: new state space has exponential sizeTackle an easier problem•Problem has two novel elements for “theory”•Discounting of reward based on arrival time•Probability distribution on outcome of actions•We will set aside second issue for now•In practice, robot can control errors•Even first issue by itself is hard and interesting•First step towards solving whole problemDiscounted-Reward TSPGiven •undirected graph G=(V,E) •edge weights (travel times) de ≥ 0•weights on nodes (rewards) rv ≥ 0•discount factor   (0,1)•root node sGoalfind a path P starting at s that maximizes total discounted reward (P) = v P rv dP(v)Approximation Algorithms•Discounted-Reward TSP is NP-complete (and so is more general MDP-type problem)•reduction from minimum latency TSP•So intractable to solve exactly•Goal: approximation algorithm that is guaranteed to collect at least some constant fraction of the best possible discounted rewardRelated ProblemsGoal of Discounted-Reward TSP seems to be to find a “short” path that collects “lots” of reward•Prize-Collecting TSP•Given a root vertex v, find a tour containing v that minimizes total length + foregone reward (undiscounted)•Primal-dual 2-approximation algorithm [GW 95]k-TSP •Find a tour of minimum length that visits at least k vertices •2-approximation algorithm known for undirected graphs based on algorithm for PC-TSP [Garg 99]•Can be extended to handle node-weighted versionMismatchConstant factor approximation on length doesn’t exponentiate well•Suppose optimum solution reaches some vertex v at time t for reward tr•Constant factor approximation would reach within time 2t for reward 2tr•Result: get only t fraction of optimum discounted reward, not a constant fraction.Orienteering ProblemFind a path of length at most D that maximizes net reward collected•Complement of k-TSP •approximates reward collected instead of length•avoids changing length, so exponentiation doesn’t hurt•unrooted case can be solved via k-TSP•Drawback: no constant factor approximation for rooted non-geometric version previously known•Our techniques also give a constant factor approximation for Orienteering problemOur ResultsUsing -approximation for k-TSP as subroutine• (3/2 +2)-approximation for Orienteering• e(3/2  + 2)-approximation for Discounted-Reward Collection•constant-factor approximations for tree- and multiple-path versions of the problemsOur ResultsUsing -approximation for k-TSP as subroutinesubstitute =2 announced by Garg in 1999• (3/2 +25 -approximation for Orienteering• e(3/2 +13-approximation for Discounted-Reward Collection•constant-factor approximations for tree- and multiple-path versions of the problemsEliminating Exponentiation•Let dv = shortest path distance (time) to v •Define the prize at v as v=dv rv•max discounted reward possibly collectable at v•If given path reaches v at time tv, define excess ev = tv – dv•diference between shortest path and chosen one•Then discounted reward at v is ev v•Idea: if excess small, prize ~ discounted reward•Fact: excess only increases as traverse path•excess reflects lost time; can’t make it upOptimum path•assume = ½ (can scale edge lengths)Claim: at least ½ of optimum path’s discounted reward R is collected before path’s excess reaches 1 suProof by contradiction:• Let u be first vertex with eu ≥ 1• Suppose more than R/2 reward follows u• Can shortcut directly to u then traverse the rest of optimum• reduces all excesses after u by at least 1• so “undiscounts” rewards by factor  -1 = 2• so doubles discounted reward collected• but this was more