  I approach the Problem of Time and other foundations of Quantum Cosmology
using a combined histories, timeless and semiclassical approach. This approach
is along the lines pursued by Halliwell. It involves the timeless probabilities
for dynamical trajectories entering regions of configuration space, which are
computed within the semiclassical regime. Moreover, the objects that Halliwell
uses in this approach commute with the Hamiltonian constraint, H. This approach
has not hitherto been considered for models that also possess nontrivial linear
constraints, Lin. This paper carries this out for some concrete relational
particle models (RPM's). If there is also commutation with Lin - the Kuchar
observables condition - the constructed objects are Dirac observables.
Moreover, this paper shows that the problem of Kuchar observables is explicitly
resolved for 1- and 2-d RPM's. Then as a first route to Halliwell's approach
for nontrivial linear constraints that is also a construction of Dirac
observables, I consider theories for which Kuchar observables are formally
known, giving the relational triangle as an example. As a second route, I apply
an indirect method that generalizes both group-averaging and Barbour's best
matching. For conceptual clarity, my study involves the simpler case of
Halliwell 2003 sharp-edged window function. I leave the elsewise-improved
softened case of Halliwell 2009 for a subsequent Paper II. Finally, I provide
comments on Halliwell's approach and how well it fares as regards the various
facets of the Problem of Time and as an implementation of QM propositions.
