AltAlt system is a domain-independent planner based on a combination of Graphplan and heuristic state space search technology. The first version of AltAlt competed in the last international planning competition (AIPS-2000). Although that version was not completely debugged, it stayed on the average with respect to the rest of the planners. AltAlt has recently been enhanced, and its performance with respect to the test suite used in the last AIPS-2000 planning competition, as well as many benchmark problems is remarkably robust. AltAlt is a hybrid planner implemented on the top of two state of the art planning systems, STAN a Graphplan-style planner and HSP-r a heuristic search planner. Basically, AltAlt uses Graphplan’s planning graph data structure to derive a family of very effective search heuristics, which are then used to drive a heuristic state search planner. The new version of AltAlt has been enhanced with a variety of optimizations to drive down the cost of heuristic computation, as well as the state search. Specifically, we have use partial constructed planning graphs to control the cost of computing the heuristics, and subsets of actions in the planning graph to limit the branching factor of regression search.