decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  29 {
  30         return this->cusp_;
  31 }
  32
  33 float ParallelSlot::DH() const
  34 {
  35         return this->DH_;
  36 }
  37
  38 PolygonObstacle &ParallelSlot::slot()
  39 {
  40         return this->slot_;
  41 }
  42
  43 float ParallelSlot::slotHeading()
  44 {
  45         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         if (!this->slotSide_) {
  57                 float y0 = this->slot().bnodes()[0]->y();
  58                 float x0 = this->slot().bnodes()[0]->x();
  59                 float y1 = this->slot().bnodes()[1]->y();
  60                 float x1 = this->slot().bnodes()[1]->x();
  61                 float y3 = this->slot().bnodes()[3]->y();
  62                 float x3 = this->slot().bnodes()[3]->x();
  63                 if (sgn((x1 - x3) * (y0 - y3) - (y1 - y3) * (x0 - x3)) < 0)
  64                         this->slotSide_ = LEFT;
  65                 else
  66                         this->slotSide_ = RIGHT;
  67         }
  68         return this->slotSide_;
  69 }
  70
  71 SlotType ParallelSlot::slotType()
  72 {
  73         if (!this->slotType_) {
  74                 float d1 = EDIST(
  75                         this->slot().bnodes()[0],
  76                         this->slot().bnodes()[1]
  77                 );
  78                 float d2 = EDIST(
  79                         this->slot().bnodes()[1],
  80                         this->slot().bnodes()[2]
  81                 );
  82                 if (d1 > d2)
  83                         this->slotType_ = PERPENDICULAR;
  84                 else
  85                         this->slotType_ = PARALLEL;
  86         }
  87         return this->slotType_;
  88 }
  89
  90 // setter
  91 void ParallelSlot::DH(float dh)
  92 {
  93         this->DH_ = dh;
  94 }
  95
  96 // other
  97 void ParallelSlot::fip()
  98 {
  99         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 100         // RRTNode.s() works as iteration level
 101         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 102
 103         // TODO add init nodes
 104         // for now just copy fpose()
 105         bool left = false; // right parking slot
 106         float di = -1;
 107         // new pose for parallel parking to right slot
 108         float tnx;
 109         float tny;
 110         float nx;
 111         float ny;
 112         // temporary tnx is angle
 113         tnx = this->slotHeading() + M_PI;
 114         if (this->slotSide() == RIGHT)
 115                 tnx -= M_PI / 4;
 116         else
 117                 tnx += M_PI / 4;
 118         nx = this->fposecenter()->x() + 0.01 * cos(tnx);
 119         ny = this->fposecenter()->y() + 0.01 * sin(tnx);
 120         BicycleCar *CC = new BicycleCar(nx, ny, this->slotHeading());
 121         // move left by car width / 2
 122         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 123         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 124         // move down
 125         nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 126         ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 127         if (this->slotSide() == LEFT) {
 128                 std::cerr << "left PS" << std::endl;
 129                 left = true;
 130                 di = 1;
 131                 // move right by car width / 2
 132                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 133                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 134                 // move down
 135                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 136                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 137         }
 138         BicycleCar *B = new BicycleCar(nx, ny, CC->h());
 139         this->DH(di * 0.01 / CC->out_radi());
 140         BicycleCar *c;
 141         int i = 0;
 142         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 143         while (!this->slot().collide(c->frame())) {
 144                 q.push(c);
 145                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 146                 i += 1;
 147         }
 148         delete c; // not in q and collide
 149         // BFS
 150         while (!q.empty()) {
 151                 c = q.front();
 152                 q.pop();
 153                 if (this->isInside(c)) {
 154                         goto createcuspandfinish;
 155                 } else if (c->s() < 9) {
 156                         BicycleCar *cc = this->flnc(c);
 157                         cc->s(c->s() + 1);
 158                         cc->bcparent(c);
 159                         q.push(cc);
 160                 } else {
 161                         delete c; // not in q and collide
 162                 }
 163         }
 164         return;
 165 createcuspandfinish:
 166         std::vector<RRTNode *> cusp;
 167         while (c) {
 168                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 169                 c = c->bcparent();
 170         }
 171         std::reverse(cusp.begin(), cusp.end());
 172         this->cusp().push_back(cusp);
 173         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 174         std::swap(q, empty);
 175 }
 176
 177 void ParallelSlot::fipr(BicycleCar *B)
 178 {
 179         // TODO for right parallel parking also
 180         // it's only for lpar scenario now
 181
 182         std::vector<RRTNode *> cusp;
 183         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 184         // just copied from fip()
 185         this->DH(-0.01 / B->out_radi());
 186         BicycleCar *c;
 187         c = this->flncr(B);
 188         while (c->lfx() < 0) {
 189                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 190                 BicycleCar *cc = this->flncr(c);
 191                 cc->s(c->s() + 1);
 192                 delete c;
 193                 c = cc;
 194         }
 195         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 196         std::reverse(cusp.begin(), cusp.end());
 197         this->cusp().push_back(cusp);
 198 }
 199
 200 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 201 {
 202         // TODO find last not colliding
 203         // for now just copy flast()
 204         RRTNode *cc;
 205         if (int(B->s()) % 2 == 0) {
 206                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 207         } else {
 208                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 209         }
 210         float di = -1;
 211         if (this->slotSide() == LEFT)
 212                 di = 1;
 213         BicycleCar *p;
 214         int i = 1;
 215         p = B->move(cc, i * di * this->DH());
 216         while (!this->slot().collide(p->frame())) {
 217                 delete p;
 218                 i += 10;
 219                 p = B->move(cc, i * this->DH());
 220         }
 221         i -= 10;
 222         p = B->move(cc, i * di * this->DH());
 223         while (!this->slot().collide(p->frame())) {
 224                 if (this->isInside(p)) {
 225                         i += 1;
 226                         break;
 227                 }
 228                 delete p;
 229                 i += 1;
 230                 p = B->move(cc, i * this->DH());
 231         }
 232         delete p;
 233         return B->move(cc, (i - 1) * this->DH());
 234 }
 235
 236 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 237 {
 238         // TODO find last not colliding
 239         // for now just copy flast()
 240         RRTNode *cc;
 241         if (int(B->s()) % 2 == 0)
 242                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 243         else
 244                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 245         BicycleCar *p;
 246         int i = 1;
 247         p = B->move(cc, i * this->DH());
 248         while (!this->slot().collide(p->frame())
 249                         && (
 250                                 (this->DH() > 0 && p->x() >= 0)
 251                                 || (this->DH() < 0 && p->lfx() <= 0)
 252                         )) {
 253                 delete p;
 254                 i += 10;
 255                 p = B->move(cc, i * this->DH());
 256         }
 257         i -= 10;
 258         p = B->move(cc, i * this->DH());
 259         while (!this->slot().collide(p->frame())) {
 260                 if (this->DH() > 0 && p->x() <= 0) {
 261                         i += 1;
 262                         break;
 263                 }
 264                 if (this->DH() < 0 && p->lfx() >= 0) {
 265                         i += 1;
 266                         break;
 267                 }
 268                 delete p;
 269                 i += 1;
 270                 p = B->move(cc, i * this->DH());
 271         }
 272         delete p;
 273         return B->move(cc, (i - 1) * this->DH());
 274 }
 275
 276 RRTNode *ParallelSlot::fposecenter()
 277 {
 278         return this->slot().bnodes().front();
 279 }
 280
 281 bool ParallelSlot::flast(
 282         RRTNode *P,
 283         bool right,
 284         int il,
 285         std::vector<RRTNode *> &cusp
 286 )
 287 {
 288         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 289         RRTNode *cc;
 290         if (right)
 291                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 292         else
 293                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 294         BicycleCar *p;
 295         int i = 1;
 296         p = B->move(cc, i * this->DH());
 297         while (!this->slot().collide(p->frame())
 298                         && (
 299                                 (this->DH() > 0 && p->x() <= 0)
 300                                 || (this->DH() < 0 && p->x() >= 0)
 301                         )) {
 302                 delete p;
 303                 i += 10;
 304                 p = B->move(cc, i * this->DH());
 305         }
 306         i -= 10;
 307         p = B->move(cc, i * this->DH());
 308         while (!this->slot().collide(p->frame())
 309                         && (
 310                                 (this->DH() > 0 && p->x() <= 0)
 311                                 || (this->DH() < 0 && p->x() >= 0)
 312                         )) {
 313                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 314                         i += 1;
 315                         break;
 316                 }
 317                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 318                         i += 1;
 319                         break;
 320                 }
 321                 delete p;
 322                 i += 1;
 323                 p = B->move(cc, i * this->DH());
 324         }
 325         delete p;
 326         p = B->move(cc, (i - 1) * this->DH());
 327         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 328                 cusp.push_back(p);
 329                 return true;
 330         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 331                 cusp.push_back(p);
 332                 return true;
 333         } else if (il < 8) {
 334                 cusp.push_back(p);
 335                 return this->flast(p, !right, il + 1, cusp);
 336         }
 337         return false;
 338 }
 339
 340 void ParallelSlot::fpose()
 341 {
 342         bool left = false; // right parking slot
 343         float di = -1;
 344         BicycleCar *CC = new BicycleCar(
 345                 this->fposecenter()->x(),
 346                 this->fposecenter()->y() - 0.01,
 347                 this->slotHeading()
 348         );
 349         BicycleCar *B = new BicycleCar(
 350                 CC->x() - CC->width() / 2,
 351                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 352                 this->slotHeading()
 353         );
 354         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 355                 left = true;
 356                 di = 1;
 357                 delete B;
 358                 B = new BicycleCar(
 359                         CC->x() + CC->width() / 2,
 360                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 361                         this->slotHeading()
 362                 );
 363         }
 364         this->DH(di * 0.01 / CC->out_radi());
 365         BicycleCar *p;
 366         int i = 0;
 367         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 368         while (!this->slot().collide(p->frame())) {
 369                 std::vector<RRTNode *> tmpcusp;
 370                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 371                 if (this->flast(p, left, 0, tmpcusp)) {
 372                         this->cusp().push_back(tmpcusp);
 373                         return;
 374                 }
 375                 i += 1;
 376                 delete p;
 377                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 378         }
 379 }
 380
 381 bool ParallelSlot::isInside(BicycleCar *c)
 382 {
 383         bool inside = true;
 384         RRTNode *tmpn;
 385         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 386         if (!this->slot().collide(tmpn))
 387                 inside = false;
 388         delete tmpn;
 389         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 390         if (!this->slot().collide(tmpn))
 391                 inside = false;
 392         delete tmpn;
 393         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 394         if (!this->slot().collide(tmpn))
 395                 inside = false;
 396         delete tmpn;
 397         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 398         if (!this->slot().collide(tmpn))
 399                 inside = false;
 400         delete tmpn;
 401         return inside;
 402 }
 403
 404 struct SamplingInfo ParallelSlot::getSamplingInfo()
 405 {
 406         struct SamplingInfo si;
 407         BicycleCar *CC = new BicycleCar(
 408                 this->fposecenter()->x(),
 409                 this->fposecenter()->y() - 0.01,
 410                 this->slotHeading()
 411         );
 412         si.x = this->slot().bnodes()[0]->x();
 413         si.y = this->slot().bnodes()[0]->y();
 414         si.r = CC->diag_radi();
 415         si.h = this->slotHeading() - acos(EDIST( // TODO generalize
 416                 this->slot().bnodes()[0],
 417                 this->slot().bnodes()[1]
 418         ) / BCAR_LENGTH);
 419         return si;
 420 }