skip to main content

Search for: All records

Creators/Authors contains: "Koenig, S."

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF. While existing work identifies a limited form of symmetries using rectangle reasoning and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows for themore »automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH with rectangle reasoning, a state-of-the-art variant of CBS, with respect to runtime and success rate.« less
  2. Many interesting search problems can be formulated as bi-objective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Bi-objective search algorithms have to maintain the set of undominated paths from the start state to each state to compute the set of paths from the start state to the goal state that are not dominated by some other path from the start state to the goal state (called the Pareto-optimal solution set). Each time they find a new path to a state s, they perform amore »dominance check to determine whether this path dominates any of the previously found paths to s or whether any of the previously found paths to s dominates this path. Existing algorithms do not perform these checks efficiently. On the other hand, our Bi-Objective A* (BOA*) algorithm requires only constant time per check. In our experimental evaluation, we show that BOA* can run an order of magnitude (or more) faster than state-of-the-art bi-objective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.« less
  3. We report on an experiment that we performed when we taught the undergraduate artificial intelligence class at the University of Southern California. We taught it - under very similar conditions - once with and once without an attendance requirement. The attendance requirement substantially increased the attendance of the students. It did not substantially affect their performance but decreased their course ratings across all categories in the official course evaluation, whose results happened to be biased toward the opinions of the students attending the lectures. For example, the overall rating of the instructor was 0.89 lower (on a 1-5 scale) withmore »the attendance requirement and the overall rating of the class was 0.85 lower. Thus, the attendance requirement, combined with the policy for administering the course evaluation, had a large impact on the course ratings, which is a problem if the course ratings influence decisions on promotions, tenure, and salary increments for the instructors but also demonstrates the potential for the manipulation of course ratings.« less