Browsing by Author "Baier, Jorge A."

Now showing 1 - 11 of 11
  • Thumbnail Image
    Item
    A heuristic search approach to planning with temporally extended preferences
    (ELSEVIER SCIENCE BV, 2009) Baier, Jorge A.; Bacchus, Fahiem; Mcllraith, Sheila A.
    Planning with preferences involves not only finding a plan that achieves the goal, it requires finding a preferred plan that achieves the goal, where preferences over plans are specified as part of the planner's input. In this paper we provide a technique for accomplishing this objective. Our technique can deal with a rich class of preferences, including so-called temporally extended preferences (TEPs). Unlike simple preferences which express desired properties of the final state achieved by a plan, TEPs can express desired properties of the entire sequence of states traversed by a plan, allowing the user to express a much richer set of preferences. Our technique involves converting a planning problem with TEPs into an equivalent planning problem containing only simple preferences. This conversion is accomplished by augmenting the inputed planning domain with a new set of predicates and actions for updating these predicates. We then provide a collection of new heuristics and a specialized search algorithm that can guide the planner towards preferred plans. Under some fairly general conditions our method is able to find a most preferred plan-i.e., an optimal plan. It can accomplish this without having to resort to admissible heuristics, which often perform poorly in practice. Nor does our technique require an assumption of restricted plan length or make-span. We have implemented our approach in the HPLAN-P planning system and used it to compete in the 5th International Planning Competition, where it achieved distinguished performance in the Qualitative Preferences track. (C) 2008 Elsevier B.V. All rights reserved.
  • Thumbnail Image
    Item
    Avoiding and Escaping Depressions in Real-Time Heuristic Search
    (AI ACCESS FOUNDATION, 2012) Hernandez, Carlos; Baier, Jorge A.
    Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA* (k), improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms, daRTAA* produces the best solutions given a fixed deadline on the average time allowed per planning episode. We prove all our algorithms have good theoretical properties: in finite search spaces, they find a solution if one exists, and converge to an optimal after a number of trials.
  • No Thumbnail Available
    Item
    Multi-Agent Path Finding: A New Boolean Encoding
    (2022) Asin Acha, Roberto; Lopez, Rodrigo; Hagedorn, Sebastian; Baier, Jorge A.
    Multi-agent pathfinding (MAPF) is an NP-hard problem. As such, dense maps may be very hard to solve optimally. In such scenarios, compilation-based approaches, via Boolean satisfiability (SAT) and answer set programming (ASP), have been shown to outperform heuristic-search-based approaches, such as conflict-based search (CBS). In this paper, we propose a new Boolean encoding for MAPF, and show how to implement it in ASP and MaxSAT. A feature that distinguishes our encoding from existing ones is that swap and follow conflicts are encoded using binary clauses, which can be exploited by current conflict -driven clause learning (CDCL) solvers. In addition, the number of clauses used to encode swap and follow conflicts do not depend on the number of agents, allowing us to scale better. For MaxSAT, we study different ways in which we may combine the MSU3 and LSU algorithms for maximum performance. In our experimental evaluation, we used square grids, ranging from 20 x 20 to 50 x 50 cells, and warehouse maps, with a varying number of agents and obstacles. We compared against representative solvers of the state-of-the-art, including the search-based algorithm CBS, the ASP-based solver ASP-MAPF, and the branch-and-cut-and-price hybrid solver, BCP. We observe that the ASP implementation of our encoding, ASP-MAPF2 outperforms other solvers in most of our experiments. The MaxSAT implementation of our encoding, MtMS shows best performance in relatively small warehouse maps when the number of agents is large, which are the instances with closer resemblance to hard puzzle-like problems.
  • No Thumbnail Available
    Item
    Planning with Preferences
    (2008) Baier, Jorge A.; McIlraith, Sheila A.
    Automated planning is a branch or AI that addresses the problem of generating a set of actions to achieve a specified goal state, given an initial state of the world. It is an active area of research that is central to the development of intelligent agents and autonomous robots. In many real-world applications, a multitude of valid plans exist, and a user distinguishes plans of high qnality by how well they adhere to the user's preferences. To generate such high-quality plans automatically, a planning system must provide a means of specifying the user's preferences with respect to the planning task, as well as a means of generating plans that ideally optimize these preferences. In the last few years, there has been significant research in the area of planning with preferences. In this article we review current approaches to preference representation for planning as well as overviewing and contrasting the various approaches to generating preferred plans that have been developed to date.
  • No Thumbnail Available
    Item
    Planning with rich goals, preferences and procedural operators via reformulation
    (2011) Baier, Jorge A.
    We summarize the main contributions of the thesis "Effective search techniques for non-classical planning via reformulation", which received an Honorable Mention for the ICAPS Best Dissertation Award, 2011. The thesis explored how to leverage state-of-the-art classical planning techniques in order to solve compelling non-classical planning problems such as planning with temporally extended goals and preferences, planning with procedural control and planning with procedural operators.
  • No Thumbnail Available
    Item
    Reconnection with the Ideal Tree: A New Approach to Real-Time Search
    (2014) Rivera, Nicolas; Illanes, Leon; Baier, Jorge A.; Hernandez, Carlos
    Many applications, ranging from video games to dynamic robotics, require solving single-agent, deterministic search problems in partially known environments under very tight time constraints. Real-Time Heuristic Search (RTHS) algorithms are specifically designed for those applications. As a subroutine, most of them invoke a standard, but bounded, search algorithm that searches for the goal. In this paper we present FRIT, a simple approach for single-agent deterministic search problems under tight constraints and partially known environments that unlike traditional RTHS does not search for the goal but rather searches for a path that connects the current state with a so-called ideal tree T. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and then carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search is done using an algorithm that is passed as a parameter to FRIT. If such a parameter is an RTHS algorithm, then the resulting algorithm can be an RTHS algorithm. We show, in addition, that FRIT may be fed with a (bounded) complete blind-search algorithm. We evaluate our approach over grid pathfinding benchmarks including game maps and mazes. Our results show that FRIT, used with RTAA*, a standard RTHS algorithm, outperforms RTAA* significantly; by one order of magnitude under tight time constraints. In addition, FRIT(daRTAA*) substantially outperforms daRTAA*, a state-of-the-art RTHS algorithm, usually obtaining solutions 50% cheaper on average when performing the same search effort. Finally, FRIT(BFS), i.e., FRIT using breadth-first-search, obtains best-quality solutions when time is limited compared to Adaptive A* and Repeated A*. Finally we show that Bug2, a pathfinding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.
  • No Thumbnail Available
    Item
    Simple and efficient bi-objective search algorithms via fast dominance checks
    (2023) Hernandez, Carlos; Yeoh, William; Baier, Jorge A.; Zhang, Han; Suazo, Luis; Koenig, Sven; Salzman, Oren
    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. Instead of looking for a single optimal path, we compute a Pareto-optimal frontier in bi-objective search, which is a set of paths in which no two paths dominate each other. Bi-objective search algorithms perform dominance checks each time a new path is discovered. Thus, the efficiency of these checks is key to performance. In this article, we propose algorithms for two kinds of bi-objective search problems. First, we consider the problem of computing the Pareto-optimal frontier of the paths that connect a given start state with a given goal state. We propose Bi-Objective A* (BOA*), a heuristic search algorithm based on A*, for this problem. Second, we consider the problem of computing one Pareto-optimal frontier for each state s of the search graph, which contains the paths that connect a given start state with s. We propose Bi-Objective Dijkstra (BOD), which is based on BOA*, for this problem. A common feature of BOA* and BOD is that all dominance checks are performed in constant time, unlike the dominance checks of previous algorithms. We show in our experimental evaluation that both BOA* and BOD are substantially faster than state-of-the-art bi-objective search algorithms. (c) 2022 Published by Elsevier B.V.
  • No Thumbnail Available
    Item
    The 2k Neighborhoods for Grid Path Planning
    (2020) Rivera, Nicolas; Hernandez, Carlos; Hormazabal, Nicolas; Baier, Jorge A.
    Grid path planning is an important problem in AI. Its understanding has been key for the development of autonomous navigation systems. An interesting and rather surprising fact about the vast literature on this problem is that only a few neighborhoods have been used when evaluating these algorithms. Indeed, only the 4- and 8-neighborhoods are usually considered, and rarely the 16-neighborhood. This paper describes three contributions that enable the construction of effective grid path planners for extended 2(k)-neighborhoods; that is, neighborhoods that admit 2(k) neighbors per state, where k is a parameter. First, we provide a simple recursive definition of the 2(k)-neighborhood in terms of the 2(k-1)-neighborhood. Second, we derive distance functions, for any k >= 2, which allow us to propose admissible heuristics that are perfect for obstacle-free grids, which generalize the well-known Manhattan and Octile distances. Third, we define the notion of canonical path for the 2(k)-neighborhood; this allows us to incorporate our neighborhoods into two versions of A*, namely Canonical A* and Jump Point Search (JPS), whose performance, we show, scales well when increasing k. Our empirical evaluation shows that, when increasing k, the cost of the solution found improves substantially. Used with the 2(k)-neighborhood, Canonical A* and JPS, in many configurations, are also superior to the any-angle path planner Theta* both in terms of solution quality and runtime. Our planner is competitive with one implementation of the any-angle path planner, ANYA in some configurations. Our main practical conclusion is that standard, well-understood grid path planning technology may provide an effective approach to any-angle grid path planning.
  • No Thumbnail Available
    Item
    The Well-being Teaching Assistant: A Proactive Approach to Caring for Students with Academic and Personal Difficulties in Massive Courses
    (American Society for Engineering Education, 2023) Baier, Jorge A.; Hilliger, Isabel; Hidalgo, Ximena; Piña, Matías; Astudillo, Gabriel
    © American Society for Engineering Education, 2023.Since the covid pandemic, some higher education institutions have promoted a flexible evaluation approach for students who face a variety of problems. Instructors willing to implement such flexibilizations face an important challenge: making themselves aware of students going through hard times. This evidence-based practice paper presents an overview and a preliminary evaluation of the well-being teaching assistant (WTA), an approach to facilitating communication, suggesting and documenting flexibilizations, and providing support for students going through difficult times in high-enrolment courses. WTAs are regular members of the teaching assistant staff, but they use an early warning system to identify potential students at risk of failure, initiate communication using supportive language, and take action by suggesting flexibilization or providing academic support for students facing challenges. WTAs have been incorporated into 27 courses at a large school of engineering in Latin America, during 2022, and have been positively evaluated by students. One of the main current challenges of the approach is scalability.
  • No Thumbnail Available
    Item
    Time-Bounded Best-First Search for Reversible and Non-reversible Search Graphs
    (2016) Hernandez, Carlos; Baier, Jorge A.; Asin, Roberto
    Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Known to outperform state-of-the-art real-time search algorithms based on Korf's Learning Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not considered as a "true" real-time search algorithm since it fails in non-reversible problems even it the goal is still reachable from the current state. In this paper we propose and study Time-Bounded Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose Restarting Time-BoundedWeighted A* (TB R (WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating "backtracking moves" and incorporating search restarts and heuristic learning. In non-reversible problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned by Time-BoundedWeighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TB R (WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TB R (WA*) on the racetrack problem. We compare our algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted heuristic. A general observation is that the performance of both TB(WA*) and TB R (WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin.
  • No Thumbnail Available
    Item
    WIP: what makes courses demanding in engineering education? A combination of mixed methods and grounded theory research
    (2020) Hilliger Carrasco, Isabel; Melian Torres, Constanza Loreto; Meza, Javiera; Cortés, Gonzalo; Baier, Jorge A.
    Engineering undergraduate programs have become demanding in terms of workload [1]. Along with class time schedules packed with lectures, laboratories, and tutorials, there are a significant number of course assignments that occur outside of class, such as team-based projects and experiential learning tasks [1]. Researchers have encouraged the incorporation of these constructivist approaches into engineering education [2], aiming to help students develop a wide range of abilities (such as complex-problem solving skills and interdisciplinary thinking [3]). However, this increasing number of assignments stresses students [4], [5], negatively affecting their learning results [1], [6]. To understand what students define as a demanding course, several researchers have explored the concepts of academic workload and course difficulty [1], [4]-[7]. So far, there is a growing body of knowledge in Canada and the U.S. regarding factors that affect how first-year students perceive workload [1]. However, little is known about how students perceive course difficulty after dealing with their transition from high school to college, and how the quality of teaching affects their approach to learning [6]. Thus, not only more studies are needed to understand how student-centered approaches could enrich learning experiences from a multi-dimensional perspective [1], [3], [4], but also to examine how these multidimensional approaches make learning more meaningful at a course level [4]. This is particularly relevant in Chile, considering that previous studies have demonstrated that students who major in science and engineering often use surface approaches to learning, focusing on course content that they believe they must memorize to meet assessment requirements [8]. This paper presents a Work-In-Progress (WIP) that is part of a larger study to understand students' perceptions on engineering courses imparted at Pontificia Universidad Catolica de Chile (PUC-Chile). The research question addressed in this paper is: What factors affect students' perceptions on demanding courses in terms of difficulty? To answer this research question, we combined mixed methods with grounded theory research (MM-GT). By MM-GT, we mean the systematic collection and integration of both qualitative and quantitative data toward the goal of theory development [9]. According to recent studies, the MM-GT research approach has become useful to develop and test theory in the fields of education [8], [9]. In this study, we plan to develop theoretical models of difficulty at a course level, following best practices of MM-GT application to provide insights for course curriculum development and teaching reflection in the field of engineering education. © American Society for Engineering Education 2020.