A Faster Algorithm for Solving One-Clock Priced Timed Games

Details A Faster Algorithm for Solving One-Clock Priced Timed Games A Faster Algorithm for Solving One-Clock Priced Timed Games

2012-01-17

arxiv.org/abs/1201.3498v1

Computer Science

Computer Science and Game Theory

Scientific paper

One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that One-clock priced timed games can be solved in time m 12^n poly(n), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2^(O(n^2+m)), due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving One-clock Priced Timed Games, based on the sweep-line technique from computational geometry. The analysis is based on the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.

Affiliated with

Also associated with

No associations

Rating

A Faster Algorithm for Solving One-Clock Priced Timed Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Faster Algorithm for Solving One-Clock Priced Timed Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Faster Algorithm for Solving One-Clock Priced Timed Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-97195